{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T16:27:07Z","timestamp":1772814427071,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T00:00:00Z","timestamp":1736380800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T00:00:00Z","timestamp":1736380800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Province of Bozen-Bolzano","award":["ISTeP"],"award-info":[{"award-number":["ISTeP"]}]},{"name":"Province of Bozen-Bolzano","award":["ISTeP"],"award-info":[{"award-number":["ISTeP"]}]},{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Temporal information plays a crucial role in many database applications, however support for queries on such data is limited. We present an index structure, termed\n                    <jats:sc>RD-index<\/jats:sc>\n                    , to support\n                    <jats:italic>range-duration queries<\/jats:italic>\n                    over interval timestamped relations, which constrain both the\n                    <jats:italic>range<\/jats:italic>\n                    of the tuples\u2019 positions on the timeline and their\n                    <jats:italic>duration<\/jats:italic>\n                    .\n                    <jats:sc>RD-index<\/jats:sc>\n                    is a grid structure in the two-dimensional space, representing the position on the timeline and the duration of timestamps, respectively. Instead of using a regular grid, we consider the data distribution for the construction of the grid in order to ensure that each grid cell contains approximately the same number of intervals.\n                    <jats:sc>RD-index<\/jats:sc>\n                    features provable bounds on the running time of all the operations, allows for a simple implementation, supports very predictable query performance, and can be constructed and queried in parallel using multithreading. We benchmark our solution on a variety of datasets and query workloads, investigating both the query rate and the behavior of the individual queries. The results show that\n                    <jats:sc>RD-index<\/jats:sc>\n                    performs better than the baselines on range-duration queries, for which it is explicitly designed. Furthermore, it outperforms state of the art indexes also on mixed workloads containing queries that constrain either only the duration or the range along with range-duration queries. Finally, the size of the\n                    <jats:sc>RD-index<\/jats:sc>\n                    is in all settings smaller than the competitors, its construction scales with the number of threads, and parallelization helps improving the runtime of expensive moderate and lowly selective queries.\n                  <\/jats:p>","DOI":"10.1007\/s10619-024-07452-6","type":"journal-article","created":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T22:11:34Z","timestamp":1736374294000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Indexing temporal relations for range-duration queries"],"prefix":"10.1007","volume":"43","author":[{"given":"Matteo","family":"Ceccarello","sequence":"first","affiliation":[]},{"given":"Anton","family":"Dign\u00f6s","sequence":"additional","affiliation":[]},{"given":"Johann","family":"Gamper","sequence":"additional","affiliation":[]},{"given":"Christina","family":"Khnaisser","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"7452_CR1","unstructured":"B\u00f6hlen, M.H., Dign\u00f6s, A., Gamper, J., Jensen, C.S.: Database technology for processing temporal data (invited paper). In TIME, volume 120 of LIPIcs, pages 2:1\u20132:7. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2018)"},{"issue":"3","key":"7452_CR2","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/2380776.2380786","volume":"41","author":"Krishna G Kulkarni","year":"2012","unstructured":"Kulkarni, Krishna G., Michels, Jan-Eike.: Temporal features in SQL: 2011. SIGMOD Rec. 41(3), 34\u201343 (2012)","journal-title":"SIGMOD Rec."},{"key":"7452_CR3","first-page":"257","volume-title":"EDBT, volume 3896 of LNCS","author":"MH B\u00f6hlen","year":"2006","unstructured":"B\u00f6hlen, M.H., Gamper, J., Jensen, C.S.: Multi-dimensional aggregation for temporal data. In: EDBT, volume 3896 of LNCS, pp. 257\u2013275. Springer, New York (2006)"},{"key":"7452_CR4","doi-asserted-by":"crossref","unstructured":"Kline, N., Snodgrass, R.T.: Computing temporal aggregates. In ICDE, pages 222\u2013231. IEEE Computer Society, (1995)","DOI":"10.1109\/ICDE.1995.380389"},{"issue":"3","key":"7452_CR5","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1109\/TKDE.2003.1198403","volume":"15","author":"Bongki Moon","year":"2003","unstructured":"Moon, Bongki, L\u00f3pez, In\u00e9s Fernando Vega., Immanuel, Vijaykumar: Efficient algorithms for large-scale temporal aggregation. IEEE Trans. Knowl. Data Eng. 15(3), 744\u2013759 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"7452_CR6","first-page":"125","volume-title":"SSTD, volume 10411 of LNCS","author":"D Piatov","year":"2017","unstructured":"Piatov, D., Helmer, S.: Sweeping-based temporal aggregation. In: SSTD, volume 10411 of LNCS, pp. 125\u2013144. Springer, New York (2017)"},{"issue":"4","key":"7452_CR7","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/s00778-020-00639-0","volume":"30","author":"Panagiotis Bouros","year":"2021","unstructured":"Bouros, Panagiotis, Mamoulis, Nikos, Tsitsigkos, Dimitrios, Terrovitis, Manolis: In-memory interval joins. VLDB J. 30(4), 667\u2013691 (2021)","journal-title":"VLDB J."},{"issue":"1","key":"7452_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00778-021-00692-3","volume":"31","author":"Anton Dign\u00f6s","year":"2022","unstructured":"Dign\u00f6s, Anton, B\u00f6hlen, Michael H., Gamper, Johann, Jensen, Christian S., Moser, Peter: Leveraging range joins for the computation of overlap joins. VLDB J. 31(1), 75\u201399 (2022)","journal-title":"VLDB J."},{"key":"7452_CR9","doi-asserted-by":"crossref","unstructured":"Piatov, D., Helmer, S., Dign\u00f6s, A.: An interval join optimized for modern hardware. In ICDE, pages 1098\u20131109. IEEE Computer Society, (2016)","DOI":"10.1109\/ICDE.2016.7498316"},{"key":"7452_CR10","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, pages 1173\u20131184. ACM, (2013)","DOI":"10.1145\/2463676.2465293"},{"key":"7452_CR11","series-title":"Lecture notes in business information processing","first-page":"51","volume-title":"eBISS","author":"MH B\u00f6hlen","year":"2017","unstructured":"B\u00f6hlen, M.H., Dign\u00f6s, A., Gamper, J., Jensen, C.S.: Temporal data management - an overview. In: eBISS. Lecture notes in business information processing, vol. 324, pp. 51\u201383. Springer, New York (2017)"},{"issue":"4","key":"7452_CR12","doi-asserted-by":"publisher","first-page":"26:1","DOI":"10.1145\/2967608","volume":"41","author":"A Dign\u00f6s","year":"2016","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-26:46 (2016)","journal-title":"ACM Trans. Database Syst."},{"key":"7452_CR13","doi-asserted-by":"crossref","unstructured":"Behrend, A., Dign\u00f6s, A., Gamper, J., Schmiegelt, P., Voigt, H., Rottmann, M., Kahl, K.: Period index: A learned 2d hash index for range and duration queries. In SSTD, pages 100\u2013109. ACM, (2019)","DOI":"10.1145\/3340964.3340965"},{"issue":"10","key":"7452_CR14","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1093\/cid\/cir063","volume":"52","author":"Y Hayashi","year":"2011","unstructured":"Hayashi, Y., Paterson, D.L.: Strategies for reduction in duration of antibiotic use in hospitalized patients. Clin. Inf. Dis. 52(10), 1232\u20131240 (2011)","journal-title":"Clin. Inf. Dis."},{"key":"7452_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1038\/s41579-021-00649-x","volume":"20","author":"DGJ Larsson","year":"2022","unstructured":"Larsson, D.G.J., Flach, C.-F.: Antibiotic resistance in the environment. Nat. Rev. Microbiol. 20, 257\u2013269 (2022)","journal-title":"Nat. Rev. Microbiol."},{"key":"7452_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.jpeds.2021.03.017","volume":"234","author":"Daniel J Shapiro","year":"2021","unstructured":"Shapiro, Daniel J., Hall, Matthew, Lipsett, Susan C., Hersh, Adam L., Ambroggio, Lilliam, Shah, Samir S., Brogan, Thomas V., Gerber, Jeffrey S., Williams, Derek J., Grijalva, Carlos G., Blaschke, Anne J., Neuman, Mark I.: Short- versus prolonged-duration antibiotics for outpatient pneumonia in children. J. Pediatr. 234, 205-211.e1 (2021)","journal-title":"J. Pediatr."},{"key":"7452_CR17","first-page":"286","volume-title":"ADBIS, volume 5739 of LNCS","author":"A Behrend","year":"2009","unstructured":"Behrend, A., Manthey, R., Sch\u00fcller, G., Wieneke, M.: Detecting moving objects in noisy radar data using a relational database. In: ADBIS, volume 5739 of LNCS, pp. 286\u2013300. Springer, New york (2009)"},{"key":"7452_CR18","doi-asserted-by":"crossref","unstructured":"Sch\u00fcller, G., Behrend, A., Manthey, R.: AIMS: an sql-based system for airspace monitoring. In GIS-IWGS, pages 31\u201338. ACM, (2010)","DOI":"10.1145\/1878500.1878508"},{"key":"7452_CR19","series-title":"volume 7503 of LNCS","first-page":"332","volume-title":"ADBIS","author":"G Sch\u00fcller","year":"2012","unstructured":"Sch\u00fcller, G., Schmiegelt, P., Behrend, A.: Supporting phase management in stream applications. In: ADBIS. volume 7503 of LNCS, pp. 332\u2013345. Springer, New York (2012)"},{"key":"7452_CR20","doi-asserted-by":"crossref","unstructured":"Persia, F., Bettini, F., Helmer, S.: An interactive framework for video surveillance event detection and modeling. In CIKM, pages 2515\u20132518. ACM, (2017)","DOI":"10.1145\/3132847.3133164"},{"key":"7452_CR21","series-title":"volume 312 of advances in intelligent systems and computing","first-page":"159","volume-title":"ADBIS (2)","author":"A Behrend","year":"2014","unstructured":"Behrend, A., Schmiegelt, P., Xie, J., Fehling, R., Ghoneimy, A., Liu, Z.H., Chan, E.S., Gawlick, D.: Temporal state management for supporting the real-time analysis of clinical data. In: ADBIS (2). volume 312 of advances in intelligent systems and computing, pp. 159\u2013170. Springer, New York (2014)"},{"key":"7452_CR22","unstructured":"Kriegel, H.-P., P\u00f6tke, M., Seidl, T.: Managing intervals efficiently in object-relational databases. In VLDB, pages 407\u2013418, (2000)"},{"key":"7452_CR23","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Dign\u00f6s, A., Gamper, J., Khnaisser, C.: Indexing temporal relations for range-duration queries. In SSDBM, pages 3:1\u20133:12. ACM, (2023)","DOI":"10.1145\/3603719.3603732"},{"issue":"1","key":"7452_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/sdata.2016.35","volume":"3","author":"AEW Johnson","year":"2016","unstructured":"Johnson, A.E.W., Pollard, T.J., Shen, L., Lehman, L.-W.H., Feng, M., Ghassemi, M., Moody, B., Szolovits, P., Celi, L.A., Mark, R.G.: Mimic-iii, a freely accessible critical care database. Sci. Data 3(1), 1\u20139 (2016)","journal-title":"Sci. Data"},{"key":"7452_CR25","unstructured":"Edelsbrunner, H.: Dynamic rectangle intersection searching. Technical Report\u00a047, Institute for Information Processing, TU Graz, Austria, (1980)"},{"key":"7452_CR26","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-662-04245-8_10","volume-title":"Computational geometry","author":"M Berg","year":"2000","unstructured":"Berg, M., Kreveld, M., Overmars, M., Schwarzkopf, OtfriedCheong: More geometric data structures. In: Computational geometry, pp. 211\u2013233. Springer, Berlin Heidelberg (2000)"},{"issue":"12","key":"7452_CR27","doi-asserted-by":"publisher","first-page":"1444","DOI":"10.14778\/2536274.2536333","volume":"6","author":"Martin Kaufmann","year":"2013","unstructured":"Kaufmann, Martin: Storing and processing temporal data in a main memory column store. Proc. VLDB Endow. 6(12), 1444\u20131449 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"7452_CR28","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Bouros, P., Mamoulis, N.: HINT: a hierarchical index for intervals in main memory. In SIGMOD, pages 1257\u20131270. ACM, (2022)","DOI":"10.1145\/3514221.3517873"},{"issue":"1","key":"7452_CR29","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/1328911.1328920","volume":"4","author":"L Arge","year":"2008","unstructured":"Arge, L., de Berg, M., Haverkort, H.J., Yi, K.: The priority r-tree: a practically efficient and worst-case optimal r-tree. ACM Trans. Algorithms 4(1), 9:1-9:30 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"7452_CR30","first-page":"322","volume-title":"SIGMOD","author":"N Beckmann","year":"1990","unstructured":"Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The r*-tree: an efficient and robust access method for points and rectangles. In: SIGMOD, pp. 322\u2013331. ACM Press, New York (1990)"},{"key":"7452_CR31","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."},{"key":"7452_CR32","volume-title":"Foundations of multidimensional and metric data structures","author":"H Samet","year":"2006","unstructured":"Samet, H.: Foundations of multidimensional and metric data structures. Morgan Kaufmann, Cambridge (2006)"},{"key":"7452_CR33","unstructured":"Ulrich, T.: Loose octrees. In Game Programming Gems, pages 444\u2013453. Charles River Media, (2000)"},{"issue":"1","key":"7452_CR34","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J\u00fcrg Nievergelt","year":"1984","unstructured":"Nievergelt, J\u00fcrg., Hinterberger, Hans, Sevcik, Kenneth C.: The grid file: an adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9(1), 38\u201371 (1984)","journal-title":"ACM Trans. Database Syst."},{"key":"7452_CR35","doi-asserted-by":"crossref","unstructured":"Kraska, T., Beutel, A., Chi, Ed.H., Dean, J., Polyzotis, N.: The case for learned index structures. In SIGMOD, pages 489\u2013504. ACM, (2018)","DOI":"10.1145\/3183713.3196909"},{"key":"7452_CR36","doi-asserted-by":"crossref","unstructured":"Ding, J., Nathan, V., Alizadeh, M., Kraska, T.: Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. CoRR, arXiv:abs\/2006.13282, (2020)","DOI":"10.14778\/3425879.3425880"},{"key":"7452_CR37","doi-asserted-by":"crossref","unstructured":"Nathan, V., Ding, J., Alizadeh, M., Kraska, T.: Learning multi-dimensional indexes. In SIGMOD, pages 985\u20131000. ACM, (2020)","DOI":"10.1145\/3318464.3380579"},{"issue":"3","key":"7452_CR38","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s00778-020-00650-5","volume":"30","author":"Danila Piatov","year":"2021","unstructured":"Piatov, Danila, Helmer, Sven, Dign\u00f6s, Anton, Persia, Fabio: Cache-efficient sweeping-based interval joins for extended allen relation predicates. VLDB J. 30(3), 379\u2013402 (2021)","journal-title":"VLDB J."},{"issue":"11","key":"7452_CR39","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.14778\/3137628.3137644","volume":"10","author":"Panagiotis Bouros","year":"2017","unstructured":"Bouros, Panagiotis, Mamoulis, Nikos: A forward scan based plane sweep algorithm for parallel interval joins. Proc. VLDB Endow. 10(11), 1346\u20131357 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"7452_CR40","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s00778-017-0456-7","volume":"26","author":"Francesco Cafagna","year":"2017","unstructured":"Cafagna, Francesco, B\u00f6hlen, Michael H.: Disjoint interval partitioning. VLDB J. 26(3), 447\u2013466 (2017)","journal-title":"VLDB J."},{"key":"7452_CR41","doi-asserted-by":"crossref","unstructured":"Dign\u00f6s, A., B\u00f6hlen, M.H., Gamper, J.: Overlap interval partition join. In SIGMOD, pages 1459\u20131470. ACM, (2014)","DOI":"10.1145\/2588555.2612175"},{"issue":"2","key":"7452_CR42","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10115-016-1004-2","volume":"52","author":"Hans-Peter Kriegel","year":"2017","unstructured":"Kriegel, Hans-Peter., Schubert, Erich, Zimek, Arthur: The (black) art of runtime evaluation: are we comparing algorithms or implementations? Knowl. Inf. Syst. 52(2), 341\u2013378 (2017)","journal-title":"Knowl. Inf. Syst."},{"key":"7452_CR43","doi-asserted-by":"crossref","unstructured":"Aum\u00fcller, M., Ceccarello, M.: Running experiments with confidence and sanity. In SISAP, volume 12440 of LNCS, pages 387\u2013395. Springer, (2020)","DOI":"10.1007\/978-3-030-60936-8_31"}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-024-07452-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10619-024-07452-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-024-07452-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T01:19:17Z","timestamp":1762132757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10619-024-07452-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,9]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["7452"],"URL":"https:\/\/doi.org\/10.1007\/s10619-024-07452-6","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"value":"0926-8782","type":"print"},{"value":"1573-7578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,9]]},"assertion":[{"value":"3 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}