{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:43Z","timestamp":1779174943802,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Projekt DEAL"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The interval join is a popular operation in temporal, spatial, and uncertain databases. The majority of interval join algorithms assume that input data reside on disk and so, their focus is to minimize the I\/O accesses. Recently, an in-memory approach based on plane sweep (PS) for modern hardware was proposed which greatly outperforms previous work. However, this approach relies on a complex data structure and its parallelization has not been adequately studied. In this article, we investigate in-memory interval joins in two directions. First, we explore the applicability of a largely ignored forward scan (FS)-based plane sweep algorithm, for single-threaded join evaluation. We propose four optimizations for FS that greatly reduce its cost, making it competitive or even faster than the state-of-the-art. Second, we study in depth the parallel computation of interval joins. We design a non-partitioning-based approach that determines independent tasks of the join algorithm to run in parallel. Then, we address the drawbacks of the previously proposed hash-based partitioning and suggest a domain-based partitioning approach that does not produce duplicate results. Within our approach, we propose a novel breakdown of the partition-joins into mini-joins to be scheduled in the available CPU threads and propose an adaptive domain partitioning, aiming at load balancing. We also investigate how the partitioning phase can benefit from modern parallel hardware. Our thorough experimental analysis demonstrates the advantage of our novel partitioning-based approach for parallel computation.<\/jats:p>","DOI":"10.1007\/s00778-020-00639-0","type":"journal-article","created":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T07:02:42Z","timestamp":1617865362000},"page":"667-691","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["In-Memory Interval Joins"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8846-4330","authenticated-orcid":false,"given":"Panagiotis","family":"Bouros","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3423-4895","authenticated-orcid":false,"given":"Nikos","family":"Mamoulis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Tsitsigkos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manolis","family":"Terrovitis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,8]]},"reference":[{"key":"639_CR1","volume-title":"Principles of Compiler Design","author":"AV Aho","year":"1977","unstructured":"Aho, A.V., Ullman, J.D.: Principles of Compiler Design. Addison-Wesley Longman, Boston (1977)"},{"key":"639_CR2","unstructured":"Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., Vitter, J.S.: Scalable sweeping-based spatial join. In: VLDB (1998)"},{"issue":"4","key":"639_CR3","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/s007780050028","volume":"5","author":"B Becker","year":"1996","unstructured":"Becker, B., Gschwind, S., Ohler, T., Seeger, B., Widmayer, P.: An asymptotically optimal multiversion b-tree. VLDB J. 5(4), 264\u2013275 (1996)","journal-title":"VLDB J."},{"key":"639_CR4","doi-asserted-by":"crossref","unstructured":"Blanas, S., Li, Y., Patel, J.M.: Design and evaluation of main memory hash join algorithms for multi-core cpus. In: SIGMOD (2011)","DOI":"10.1145\/1989323.1989328"},{"issue":"11","key":"639_CR5","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"},{"key":"639_CR6","unstructured":"Bouros, P., Mamoulis, N.: Interval count semi-joins. In: EDBT (2018)"},{"key":"639_CR7","doi-asserted-by":"crossref","unstructured":"Brinkhoff, T., Kriegel, H., Seeger, B.: Efficient processing of spatial joins using r-trees. In: SIGMOD (1993)","DOI":"10.1145\/170035.170075"},{"issue":"3","key":"639_CR8","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."},{"key":"639_CR9","unstructured":"Chawda, B., Gupta, H., Negi, S., Faruquie, T.A., Subramaniam, L.V., Mohania, M.K.: Processing interval joins on map-reduce. In: EDBT (2014)"},{"key":"639_CR10","unstructured":"Chekol, M.W., Pirr\u00f2, G., Stuckenschmidt, H.: Fast interval joins for temporal SPARQL queries. In: WWW (2019)"},{"key":"639_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, R., Singh, S., Prabhakar, S., Shah, R., Vitter, J.S., Xia, Y.: Efficient join processing over uncertain data. In: CIKM (2006)","DOI":"10.1145\/1183614.1183719"},{"key":"639_CR12","doi-asserted-by":"crossref","unstructured":"Copeland, G.P., Khoshafian, S.: A decomposition storage model. In: SIGMOD (1985)","DOI":"10.1145\/318898.318923"},{"key":"639_CR13","doi-asserted-by":"crossref","unstructured":"Dign\u00f6s, A., B\u00f6hlen, M.H., Gamper, J.: Overlap interval partition join. In: SIGMOD (2014)","DOI":"10.1145\/2588555.2612175"},{"key":"639_CR14","unstructured":"Dittrich, J., Seeger, B.: Data redundancy and duplicate detection in spatial join processing. In: ICDE, pp. 535\u2013546 (2000)"},{"key":"639_CR15","doi-asserted-by":"crossref","unstructured":"Enderle, J., Hampel, M., Seidl, T.: Joining interval data in relational databases. In: SIGMOD (2004)","DOI":"10.1145\/1007568.1007645"},{"issue":"1","key":"639_CR16","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."},{"issue":"2","key":"639_CR17","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"639_CR18","unstructured":"Gunadhi, H., Segev, A.: Query processing algorithms for temporal intersection joins. In: ICDE (1991)"},{"issue":"1","key":"639_CR19","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jtbi.2010.11.033","volume":"271","author":"L Isella","year":"2011","unstructured":"Isella, L., Stehl\u00e9, J., Barrat, A., Cattuto, C., Pinton, J.F., den Broeck, W.V.: What\u2019s in a crowd? Analysis of face-to-face behavioral networks. J. Theor. Biol. 271(1), 166\u2013180 (2011)","journal-title":"J. Theor. Biol."},{"key":"639_CR20","unstructured":"Jagadish, H.V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K.C., Suel, T.: Optimal histograms with quality guarantees. In: VLDB (1998)"},{"key":"639_CR21","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: SIGMOD (2013)","DOI":"10.1145\/2463676.2465293"},{"key":"639_CR22","doi-asserted-by":"crossref","unstructured":"Kriegel, H., Kunath, P., Pfeifle, M., Renz, M.: Distributed intersection join of complex interval sequences. In: DASFAA (2005)","DOI":"10.1007\/11408079_68"},{"key":"639_CR23","unstructured":"Kriegel, H., P\u00f6tke, M., Seidl, T.: Managing intervals efficiently in object-relational databases. In: VLDB (2000)"},{"key":"639_CR24","unstructured":"Leung, T.Y.C., Muntz, R.R.: Temporal query processing and optimization in multiprocessor database machines. In: VLDB (1992)"},{"key":"639_CR25","doi-asserted-by":"crossref","unstructured":"Monacchi, A., Egarter, D., Elmenreich, W., D\u2019Alessandro, S., Tonello, A.M.: GREEND: an energy consumption dataset of households in italy and austria. In: SmartGridComm (2014)","DOI":"10.1109\/SmartGridComm.2014.7007698"},{"issue":"3","key":"639_CR26","first-page":"744","volume":"15","author":"B Moon","year":"2003","unstructured":"Moon, B., L\u00f3pez, I.F.V., Immanuel, V.: Efficient algorithms for large-scale temporal aggregation. TKDE 15(3), 744\u2013759 (2003)","journal-title":"TKDE"},{"key":"639_CR27","unstructured":"Nicolau, A.: Loop quantization: Unwinding for fine-grain parallelism exploitation. Tech. Rep. TR85-709, Dept. of Computer Science, Cornell University (1985)"},{"key":"639_CR28","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198515760.001.0001","volume-title":"Introduction to Parallel Computing","author":"WP Petersen","year":"2004","unstructured":"Petersen, W.P., Arbenz, P.: Introduction to Parallel Computing. Oxford Press, Oxford (2004)"},{"key":"639_CR29","doi-asserted-by":"crossref","unstructured":"Piatov, D., Helmer, S., Dign\u00f6s, A.: An interval join optimized for modern hardware. In: ICDE (2016)","DOI":"10.1109\/ICDE.2016.7498316"},{"key":"639_CR30","doi-asserted-by":"crossref","unstructured":"Poosala, V., Ioannidis, Y.E., Haas, P.J., Shekita, E.J.: Improved histograms for selectivity estimation of range predicates. In: SIGMOD (1996)","DOI":"10.1145\/233269.233342"},{"key":"639_CR31","volume-title":"Computational Geometry\u2014An Introduction. Texts and Monographs in Computer Science","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry\u2014An Introduction. Texts and Monographs in Computer Science. Springer, Berlin (1985)"},{"key":"639_CR32","unstructured":"Segev, A., Gunadhi, H.: Event-join optimization in temporal relational databases. In: VLDB (1989)"},{"key":"639_CR33","doi-asserted-by":"crossref","unstructured":"Sitzmann, I., Stuckey, P.J.: Improving temporal joins using histograms. In: DEXA (2000)","DOI":"10.1007\/3-540-44469-6_46"},{"key":"639_CR34","unstructured":"Soo, M.D., Snodgrass, R.T., Jensen, C.S.: Efficient evaluation of the valid-time natural join. In: ICDE (1994)"},{"key":"639_CR35","unstructured":"Stonebraker, M., Abadi, D.J., Batkin, A., Chen, X., Cherniack, M., Ferreira, M., Lau, E., Lin, A., Madden, S., O\u2019Neil, E.J., O\u2019Neil, P.E., Rasin, A., Tran, N., Zdonik, S.B.: C-store: a column-oriented DBMS. In: VLDB (2005)"},{"key":"639_CR36","doi-asserted-by":"crossref","unstructured":"Tsitsigkos, D., Bouros, P., Mamoulis, N., Terrovitis, M.: Parallel in-memory evaluation of spatial joins. In: SIGSPATIAL (2019)","DOI":"10.1145\/3347146.3359343"},{"key":"639_CR37","unstructured":"Zhang, D., Tsotras, V.J., Seeger, B.: Efficient temporal join processing using indices. In: ICDE (2002)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00639-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-020-00639-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00639-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T08:15:55Z","timestamp":1624954555000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-020-00639-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,8]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["639"],"URL":"https:\/\/doi.org\/10.1007\/s00778-020-00639-0","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,8]]},"assertion":[{"value":"13 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}