{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T21:58:07Z","timestamp":1773784687196,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T00:00:00Z","timestamp":1613174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T00:00:00Z","timestamp":1613174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006447","name":"Universit\u00e4t Z\u00fcrich","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006447","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop a family of efficient plane-sweeping interval join algorithms for evaluating a wide range of interval predicates such as Allen\u2019s relationships and parameterized relationships. Our technique is based on a framework, components of which can be flexibly combined in different manners to support the required interval relation. In temporal databases, our algorithms can exploit a well-known and flexible access method, the Timeline Index, thus expanding the set of operations it supports even further. Additionally, employing a compact data structure, the gapless hash map, we utilize the CPU cache efficiently. In an experimental evaluation, we show that our approach is several times faster and scales better than state-of-the-art techniques, while being much better suited for real-time event processing.<\/jats:p>","DOI":"10.1007\/s00778-020-00650-5","type":"journal-article","created":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T04:03:09Z","timestamp":1613275389000},"page":"379-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Cache-efficient sweeping-based interval joins for extended Allen relation predicates"],"prefix":"10.1007","volume":"30","author":[{"given":"Danila","family":"Piatov","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9666-1932","authenticated-orcid":false,"given":"Sven","family":"Helmer","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7621-967X","authenticated-orcid":false,"given":"Anton","family":"Dign\u00f6s","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1798-0215","authenticated-orcid":false,"given":"Fabio","family":"Persia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,13]]},"reference":[{"key":"650_CR1","unstructured":"The webkit open source project. https:\/\/webkit.org\/ (2012)"},{"key":"650_CR2","doi-asserted-by":"crossref","unstructured":"Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), (1983)","DOI":"10.1145\/182.358434"},{"issue":"3","key":"650_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.artmed.2013.03.006","volume":"58","author":"MR \u00c1lvarez","year":"2013","unstructured":"\u00c1lvarez, M.R., F\u00e9lix, P., Cari Nena, P.: Discovering metric temporal constraint networks on temporal databases. Artif. Intell. Med. 58(3), 139\u2013154 (2013)","journal-title":"Artif. Intell. Med."},{"key":"650_CR4","unstructured":"Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., and Vitter, J.S.: Scalable sweeping-based spatial join. In: VLDB (1998)"},{"key":"650_CR5","doi-asserted-by":"crossref","unstructured":"Behrend, A., and Sch\u00fcller, G.: A case study in optimizing continuous queries using the magic update technique. In: SSDBM (2014)","DOI":"10.1145\/2618243.2618285"},{"key":"650_CR6","doi-asserted-by":"crossref","unstructured":"Bettini, F., Persia, F., and Helmer, S.: An interactive framework for video surveillance event detection and modeling. In: CIKM (2017)","DOI":"10.1145\/3132847.3133164"},{"key":"650_CR7","doi-asserted-by":"crossref","unstructured":"Blakeley, J.A., McKenna, W.J., and Graefe, G.: Experiences building the open OODB query optimizer. In: SIGMOD (1993)","DOI":"10.1145\/170035.170080"},{"key":"650_CR8","doi-asserted-by":"crossref","unstructured":"Bouros, P., Mamoulis, N.: A forward scan based plane sweep algorithm for parallel interval joins. PVLDB 10(11), (2017)","DOI":"10.14778\/3137628.3137644"},{"key":"650_CR9","unstructured":"Bouros, P., and Mamoulis, N.: Interval count semi-joins. In: EDBT (2018)"},{"key":"650_CR10","unstructured":"Chawda, B., Gupta, H., Negi, S., Faruquie, T.A., Subramaniam, L.V., and Mohania, M.: Processing interval joins on map-reduce. In: EDBT (2014)"},{"key":"650_CR11","unstructured":"Chekol, M.W., Pirr\u00f2, G., and Stuckenschmidt, H.: Fast interval joins for temporal SPARQL queries. In: Companion of WWW, pp 1148\u20131154 (2019)"},{"key":"650_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1\u20133","key":"650_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0004-3702(91)90006-6","volume":"49","author":"R Dechter","year":"1991","unstructured":"Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artif. Intell. 49(1\u20133), 61\u201395 (1991)","journal-title":"Artif. Intell."},{"key":"650_CR14","doi-asserted-by":"crossref","unstructured":"Dign\u00f6s, A., B\u00f6hlen, M.H., and Gamper, J.: Overlap interval partition join. In: SIGMOD (2014)","DOI":"10.1145\/2588555.2612175"},{"issue":"1\u20132","key":"650_CR15","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0004-3702(92)90090-K","volume":"54","author":"C Freksa","year":"1992","unstructured":"Freksa, C.: Temporal reasoning based on semi-intervals. Artif. Intell. 54(1\u20132), 199\u2013227 (1992)","journal-title":"Artif. Intell."},{"key":"650_CR16","doi-asserted-by":"crossref","unstructured":"Gao, D., Jensen, C.S., Snodgrass, R., and Soo, M.D.: Join operations in temporal databases. VLDB J. 14(1), (2005)","DOI":"10.1007\/s00778-003-0111-3"},{"key":"650_CR17","unstructured":"Gendrano, J.A.G., Shah, R., Snodgrass, R.T., and Yang, J.: University information system (UIS) dataset. TimeCenter CD-1, (1998)"},{"key":"650_CR18","unstructured":"Gunadhi, H., and Segev, A.: Query processing algorithms for temporal intersection joins. In: ICDE (1991)"},{"key":"650_CR19","unstructured":"Helmer, S.: An interval-based index structure for structure elucidation in chemical databases. In: IFSA (2007)"},{"key":"650_CR20","doi-asserted-by":"crossref","unstructured":"Helmer, S., Persia, F.: ISEQL, an interval-based surveillance event query language. IJMDEM 7(4), (2016)","DOI":"10.4018\/IJMDEM.2016100101"},{"issue":"3","key":"650_CR21","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1002\/widm.1122","volume":"4","author":"F H\u00f6ppner","year":"2014","unstructured":"H\u00f6ppner, F., Peter, S.: Temporal interval pattern languages to characterize time flow. WIREs Data Min. Knowl. Discov. 4(3), 196\u2013212 (2014)","journal-title":"WIREs Data Min. Knowl. Discov."},{"issue":"1","key":"650_CR22","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1109\/69.755613","volume":"11","author":"CS Jensen","year":"1999","unstructured":"Jensen, C.S., Snodgrass, R.T.: Temporal data management. IEEE Trans. Knowl. Data Eng. 11(1), 36\u201344 (1999)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"650_CR23","unstructured":"Kaufmann, M.: Storing and processing temporal data in main memory column stores. PhD thesis, ETH Zurich (2014)"},{"key":"650_CR24","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Fischer, P.M., May, N., Ge, C., Goel, A.K., and Kossmann, D.: Bi-temporal timeline index: a data structure for processing queries on bi-temporal data. In: ICDE (2015)","DOI":"10.1109\/ICDE.2015.7113307"},{"key":"650_CR25","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Manjili, A.A., Vagenas, P., Fischer, P.M., Kossmann, D., F\u00e4rber, F., and 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":"650_CR26","doi-asserted-by":"crossref","unstructured":"Khayyat, Z., Lucia, W., Singh, M., Ouzzani, M., Papotti, P., Quian\u00e9-Ruiz, J.-A. Tang, N., and Kalnis, P.: Fast and scalable inequality joins. VLDB J. 26(1), (2017)","DOI":"10.1007\/s00778-016-0441-6"},{"key":"650_CR27","doi-asserted-by":"crossref","unstructured":"K\u00f6rber, M., Glombiewski, N., Morgen, A., and Seeger, B.: Tpstream: low-latency and high-throughput temporal pattern matching on event streams. Distrib. Parallel Databases (2019)","DOI":"10.1007\/s10619-019-07272-z"},{"key":"650_CR28","unstructured":"K\u00f6rber, M. Glombiewski, N., and Seeger, B.: Tpstream: Low-latency temporal pattern matching on event streams. In: EDBT pp 313\u2013324, (2018)"},{"issue":"3","key":"650_CR29","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 Rec. 41(3), 34\u201343 (2012)","journal-title":"SIGMOD Rec."},{"key":"650_CR30","volume-title":"Query Processing for Temporal Databases. Technical Report CSD-890020","author":"TYC Leung","year":"1989","unstructured":"Leung, T.Y.C., Muntz, R.R.: Query Processing for Temporal Databases. Technical Report CSD-890020. University of California, California (1989)"},{"key":"650_CR31","unstructured":"Leung, T.Y.C., and Muntz, R.R.: Query processing for temporal databases. In ICDE (1990)"},{"key":"650_CR32","unstructured":"Leung, T.Y.C., and Muntz, R.R.: Temporal query processing and optimization in multiprocessor database machines. In: VLDB (1992)"},{"issue":"1","key":"650_CR33","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1093\/comjnl\/bxh151","volume":"49","author":"J Ma","year":"2006","unstructured":"Ma, J., Hayes, P.J.: Primitive intervals versus point-based intervals: Rivals or allies? Comput. J. 49(1), 32\u201341 (2006)","journal-title":"Comput. J."},{"key":"650_CR34","doi-asserted-by":"crossref","unstructured":"Moore, S., and Ralph, J.: User-defined events for hardware performance monitoring. In: ICCS Workshop (2011)","DOI":"10.1016\/j.procs.2011.04.229"},{"key":"650_CR35","doi-asserted-by":"crossref","unstructured":"Piatov, D., and Helmer, S.: Sweeping-based temporal aggregation. In: SSTD (2017)","DOI":"10.1007\/978-3-319-64367-0_7"},{"key":"650_CR36","doi-asserted-by":"crossref","unstructured":"Piatov, D., Helmer, S., and Dign\u00f6s, A.: An interval join optimized for modern hardware. In: ICDE (2016)","DOI":"10.1109\/ICDE.2016.7498316"},{"key":"650_CR37","doi-asserted-by":"crossref","unstructured":"Pilourdault, J., Leroy, V., and Amer-Yahia, S.: Distributed evaluation of top-k temporal joins. In: SIGMOD (2016)","DOI":"10.1145\/2882903.2882912"},{"key":"650_CR38","unstructured":"Segev, A., and Gunadhi, H.: Event-join optimization in temporal relational databases. In: VLDB (1989)"},{"issue":"11","key":"650_CR39","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1016\/j.datak.2009.06.010","volume":"68","author":"S-Y Wu","year":"2009","unstructured":"Wu, S.-Y., Chen, Y.-L.: Discovering hybrid temporal patterns from sequences consisting of point- and interval-based events. Data Knowl. Eng. 68(11), 1309\u20131330 (2009)","journal-title":"Data Knowl. Eng."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00650-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-020-00650-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00650-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T07:12:34Z","timestamp":1622185954000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-020-00650-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,13]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["650"],"URL":"https:\/\/doi.org\/10.1007\/s00778-020-00650-5","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,13]]},"assertion":[{"value":"27 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}