{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T04:54:51Z","timestamp":1762145691961,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Autonomous Province of Bozen\/Bolzano","award":["ISTeP"],"award-info":[{"award-number":["ISTeP"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Joins are essential and potentially expensive operations in database management systems. When data is associated with time periods, joins commonly include predicates that require pairs of argument tuples to overlap in order to qualify for the result. Our goal is to enable built-in systems support for such joins. In particular, we present an approach where overlap joins are formulated as unions of range joins, which are more general purpose joins compared to overlap joins, i.e., are useful in their own right, and are supported well by B+-trees. The approach is sufficiently flexible that it also supports joins with additional equality predicates, as well as open, closed, and half-open time periods over discrete and continuous domains, thus offering both generality and simplicity, which is important in a system setting. We provide both a stand-alone solution that performs on par with the state-of-the-art and a DBMS embedded solution that is able to exploit standard indexing and clearly outperforms existing DBMS solutions that depend on specialized indexing techniques. We offer both analytical and empirical evaluations of the proposals. The empirical study includes comparisons with pertinent existing proposals and offers detailed insight into the performance characteristics of the proposals.<\/jats:p>","DOI":"10.1007\/s00778-021-00692-3","type":"journal-article","created":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T03:27:55Z","timestamp":1630121275000},"page":"75-99","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Leveraging range joins for the computation of overlap joins"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7621-967X","authenticated-orcid":false,"given":"Anton","family":"Dign\u00f6s","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3694-9026","authenticated-orcid":false,"given":"Michael H.","family":"B\u00f6hlen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7128-507X","authenticated-orcid":false,"given":"Johann","family":"Gamper","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9697-7670","authenticated-orcid":false,"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Moser","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,28]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Al-Kateb, M., Ghazal, A., Crolotte, A., Bhashyam, R., Chimanchode, J., Pakala, S.P.: Temporal query processing in teradata. In: Proceedings of the 16th International Conference on Extending Database Technology, EDBT 2013, pp. 573\u2013578 (2013)","key":"692_CR1","DOI":"10.1145\/2452376.2452443"},{"issue":"2\u20133","key":"692_CR2","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1023\/A:1012809914301","volume":"17","author":"WG Aref","year":"2001","unstructured":"Aref, W.G., Ilyas, I.F.: SP-GiST: an extensible database index for supporting space partitioning trees. J. Intell. Inf. Syst. 17(2\u20133), 215\u2013240 (2001)","journal-title":"J. Intell. Inf. Syst."},{"key":"692_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indices. Acta Inf. 1, 173\u2013189 (1972)","journal-title":"Acta Inf."},{"doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H., Schneider, R., Seeger, B.: The r*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, SIGMOD 1990, pp. 322\u2013331. ACM Press (1990)","key":"692_CR4","DOI":"10.1145\/93605.98741"},{"doi-asserted-by":"crossref","unstructured":"B\u00f6hlen, M.H., Dign\u00f6s, A., Gamper, J., Jensen, C.S.: Temporal data management - an overview. In: Business Intelligence and Big Data, volume 324 of Lecture Notes in Business Information Processing, pp. 51\u201383. Springer (2018)","key":"692_CR5","DOI":"10.1007\/978-3-319-96655-7_3"},{"issue":"11","key":"692_CR6","first-page":"1346","volume":"10","author":"P Bouros","year":"2017","unstructured":"Bouros, P., Mamoulis, N.: A forward scan based plane sweep algorithm for parallel interval joins. PVLDB 10(11), 1346\u20131357 (2017)","journal-title":"PVLDB"},{"doi-asserted-by":"crossref","unstructured":"Bouros, P., Mamoulis, N., Tsitsigkos, D., Terrovitis, M.: In-memory interval joins. The VLDB J. (to appear), https:\/\/pbour.github.io\/docs\/vldbj20b.pdf (2020)","key":"692_CR7","DOI":"10.1007\/s00778-020-00639-0"},{"doi-asserted-by":"crossref","unstructured":"Brinkhoff, T., Kriegel, H., Seeger, B.: Efficient processing of spatial joins using r-trees. In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, SIGMOD 1993, pp. 237\u2013246. ACM Press (1993)","key":"692_CR8","DOI":"10.1145\/170036.170075"},{"issue":"3","key":"692_CR9","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s00778-017-0456-7","volume":"26","author":"F Cafagna","year":"2017","unstructured":"Cafagna, F., B\u00f6hlen, M.H.: Disjoint interval partitioning. VLDB J. 26(3), 447\u2013466 (2017)","journal-title":"VLDB J."},{"unstructured":"Davis, J.: Temporal data management in postgresql: past, present, and future. https:\/\/doi.org\/10.5446\/19033. PGCon 2012 (2012)","key":"692_CR10"},{"doi-asserted-by":"crossref","unstructured":"Dign\u00f6s, A., B\u00f6hlen, M.H., Gamper, J.: Temporal alignment. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, pp 433\u2013444. ACM (2012)","key":"692_CR11","DOI":"10.1145\/2213836.2213886"},{"doi-asserted-by":"crossref","unstructured":"Dign\u00f6s, A., B\u00f6hlen, M.H., Gamper, J.: Overlap interval partition join. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2014, pp. 1459\u20131470 (2014)","key":"692_CR12","DOI":"10.1145\/2588555.2612175"},{"doi-asserted-by":"crossref","unstructured":"Dign\u00f6s, A., B\u00f6hlen, M.H., Gamper, J., Jensen, C.S.: Extending the kernel of a relational DBMS with comprehensive support for sequenced temporal queries. ACM Trans. Database Syst., 41(4):26:1\u201326:46 (2016)","key":"692_CR13","DOI":"10.1145\/2967608"},{"issue":"6","key":"692_CR14","doi-asserted-by":"publisher","first-page":"639","DOI":"10.14778\/3311880.3311882","volume":"12","author":"A Dign\u00f6s","year":"2019","unstructured":"Dign\u00f6s, A., Glavic, B., Niu, X., Gamper, J., B\u00f6hlen, M.H.: Snapshot semantics for temporal multiset relations. Proc. VLDB Endow. 12(6), 639\u2013652 (2019)","journal-title":"Proc. VLDB Endow."},{"unstructured":"Edelsbrunner, H.: Dynamic Rectangle Intersection Searching. Institute for Information Processing Report 47. Technical University of Graz, Austria (1980)","key":"692_CR15"},{"doi-asserted-by":"crossref","unstructured":"Enderle, J., Hampel, M., Seidl, T.: Joining interval data in relational databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2004, pp. 683\u2013694 (2004)","key":"692_CR16","DOI":"10.1145\/1007568.1007645"},{"key":"692_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"RA Finkel","year":"1974","unstructured":"Finkel, R.A., Bentley, J.L.: Quad trees: a data structure for retrieval on composite keys. Acta Inf. 4, 1\u20139 (1974)","journal-title":"Acta Inf."},{"issue":"1","key":"692_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/s00778-003-0111-3","volume":"14","author":"D Gao","year":"2005","unstructured":"Gao, D., Jensen, C.S., Snodgrass, R.T., Soo, M.D.: Join operations in temporal databases. VLDB J. 14(1), 2\u201329 (2005)","journal-title":"VLDB J."},{"unstructured":"Gendrano, J.A.G., Shah, R., Snodgrass, R.T., Yang, J.: University information system (UIS) dataset. TimeCenter CD-1 (1998)","key":"692_CR19"},{"doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, SIGMOD 1984, pp. 47\u201357. ACM Press (1984)","key":"692_CR20","DOI":"10.1145\/971697.602266"},{"issue":"4","key":"692_CR21","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/69.536250","volume":"8","author":"CS Jensen","year":"1996","unstructured":"Jensen, C.S., Snodgrass, R.T., Soo, M.D.: Extending existing dependency theory to temporal databases. IEEE Trans. Knowl. Data Eng. 8(4), 563\u2013582 (1996)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Manjili, A.A., Vagenas, P., Fischer, P.M., Kossmann, D., F\u00e4rber, F., May, N.: Timeline index: a unified data structure for processing queries on temporal data in SAP HANA. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, pp. 1173\u20131184 (2013)","key":"692_CR22","DOI":"10.1145\/2463676.2465293"},{"issue":"12","key":"692_CR23","first-page":"1210","volume":"6","author":"M Kaufmann","year":"2013","unstructured":"Kaufmann, M., Vagenas, P., Fischer, P.M., Kossmann, D., F\u00e4rber, F.: Comprehensive and interactive temporal query processing with SAP HANA. PVLDB 6(12), 1210\u20131213 (2013)","journal-title":"PVLDB"},{"issue":"13","key":"692_CR24","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.14778\/2831360.2831362","volume":"8","author":"Z Khayyat","year":"2015","unstructured":"Khayyat, Z., Lucia, W., Singh, M., Ouzzani, M., Papotti, P., Quian\u00e9-Ruiz, J., Tang, N., Kalnis, P.: Lightning fast and space efficient inequality joins. Proc. VLDB Endow. 8(13), 2074\u20132085 (2015)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"692_CR25","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00778-016-0441-6","volume":"26","author":"Z Khayyat","year":"2017","unstructured":"Khayyat, Z., Lucia, W., Singh, M., Ouzzani, M., Papotti, P., Quian\u00e9-Ruiz, J., Tang, N., Kalnis, P.: Fast and scalable inequality joins. VLDB J. 26(1), 125\u2013150 (2017)","journal-title":"VLDB J."},{"unstructured":"Kornacker, M.: Access methods for next-generation database systems. Ph.D. thesis, University of California, Berkeley. AAI9994590 (2000)","key":"692_CR26"},{"unstructured":"Kriegel, H., P\u00f6tke, M., Seidl, T.: Managing intervals efficiently in object-relational databases. In: Proceedings of 26th International Conference on Very Large Data Bases, VLDB 2000, pp. 407\u2013418 (2000)","key":"692_CR27"},{"issue":"3","key":"692_CR28","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/2380776.2380786","volume":"41","author":"KG Kulkarni","year":"2012","unstructured":"Kulkarni, K.G., Michels, J.: Temporal features in SQL: 2011. SIGMOD Record 41(3), 34\u201343 (2012)","journal-title":"SIGMOD Record"},{"issue":"5","key":"692_CR29","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1007\/s11390-018-1872-x","volume":"33","author":"J Luo","year":"2018","unstructured":"Luo, J., Shi, S., Yang, G., Wang, H., Li, J.: O2ijoin: an efficient index-based algorithm for overlap interval join. J. Comput. Sci. Technol. 33(5), 1023\u20131038 (2018)","journal-title":"J. Comput. Sci. Technol."},{"unstructured":"Microsoft. SQL Server 2016 - temporal tables. https:\/\/docs.microsoft.com\/en-us\/sql\/relational-databases\/tables\/temporal-tables (2016)","key":"692_CR30"},{"unstructured":"Oracle. Database development guide - temporal validity support. https:\/\/docs.oracle.com\/database\/121\/ADFNS\/adfns_design.htm#ADFNS967 (2016)","key":"692_CR31"},{"doi-asserted-by":"crossref","unstructured":"Petkovic, D.: Modern temporal data models: strengths and weaknesses. In: Beyond Databases, Architectures and Structures\u201411th International Conference, BDAS 2015, Ustro\u0144, Poland, May 26\u201329, 2015, Proceedings, volume 521 of Communications in Computer and Information Science, pp. 136\u2013146. Springer (2015)","key":"692_CR32","DOI":"10.1007\/978-3-319-18422-7_12"},{"issue":"8","key":"692_CR33","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/3209210","volume":"61","author":"A Petrov","year":"2018","unstructured":"Petrov, A.: Algorithms behind modern storage systems. Commun. ACM 61(8), 38\u201344 (2018)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Piatov, D., Helmer, S., Dign\u00f6s, A.: An interval join optimized for modern hardware. In: Proceedings of the 32nd IEEE International Conference on Data Engineering, ICDE 2016, pp. 1098\u20131109 (2016)","key":"692_CR34","DOI":"10.1109\/ICDE.2016.7498316"},{"unstructured":"PostgreSQL. Documentation manual PostgreSQL - range types. https:\/\/www.postgresql.org\/docs\/10\/static\/rangetypes.html (2018)","key":"692_CR35"},{"unstructured":"Saracco, C., Nicola, M., Gandhi, L.: A matter of time: Temporal data management in db2 10. http:\/\/www.ibm.com\/developerworks\/data\/library\/techarticle\/dm-1204db2temporaldata\/dm-1204db2temporaldata-pdf.pdf (2012)","key":"692_CR36"},{"unstructured":"WebKit open source project. http:\/\/www.webkit.org (2016)","key":"692_CR37"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00692-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00692-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00692-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T11:07:15Z","timestamp":1643368035000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00692-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,28]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["692"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00692-3","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2021,8,28]]},"assertion":[{"value":"14 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}