Indexing Temporal Relations for Range-Duration Queries
Article No.: 3, Pages 1 - 12
Abstract
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 RD-index, to support range-duration queries over interval timestamped relations, which constrain both the range of the tuples’ positions on the timeline and their duration. RD-index 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. RD-index features provable bounds on the running time of all the operations, allow for a simple implementation, and supports very predictable query performance. 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 RD-index 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 RD-index is in all settings smaller than the competitors.
References
[1]
Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi. 2008. The priority R-tree: A practically efficient and worst-case optimal R-tree. ACM Trans. Algorithms 4, 1 (2008), 9:1–9:30.
[2]
Martin Aumüller and Matteo Ceccarello. 2020. Running Experiments with Confidence and Sanity. In SISAP(LNCS, Vol. 12440). Springer, 387–395.
[3]
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD. ACM Press, 322–331.
[4]
Andreas Behrend, Anton Dignös, Johann Gamper, Philip Schmiegelt, Hannes Voigt, Matthias Rottmann, and Karsten Kahl. 2019. Period Index: A Learned 2D Hash Index for Range and Duration Queries. In SSTD. ACM, 100–109.
[5]
Andreas Behrend, Rainer Manthey, Gereon Schüller, and Monika Wieneke. 2009. Detecting Moving Objects in Noisy Radar Data Using a Relational Database. In ADBIS(LNCS, Vol. 5739). Springer, 286–300.
[6]
Andreas Behrend, Philip Schmiegelt, Jingquan Xie, Ronny Fehling, Adel Ghoneimy, Zhen Hua Liu, Eric S. Chan, and Dieter Gawlick. 2014. Temporal State Management for Supporting the Real-Time Analysis of Clinical Data. In ADBIS (2)(Advances in Intelligent Systems and Computing, Vol. 312). Springer, 159–170.
[7]
Mark Berg, Marc Kreveld, Mark Overmars, and OtfriedCheong Schwarzkopf. 2000. More Geometric Data Structures. In Computational Geometry. Springer Berlin Heidelberg, 211–233.
[8]
Michael H. Böhlen, Anton Dignös, Johann Gamper, and Christian S. Jensen. 2017. Temporal Data Management - An Overview. In eBISS(Lecture Notes in Business Information Processing, Vol. 324). Springer, 51–83.
[9]
Michael H. Böhlen, Johann Gamper, and Christian S. Jensen. 2006. Multi-dimensional Aggregation for Temporal Data. In EDBT(LNCS, Vol. 3896). Springer, 257–275.
[10]
Panagiotis Bouros and Nikos Mamoulis. 2017. A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins. Proc. VLDB Endow. 10, 11 (2017), 1346–1357.
[11]
Panagiotis Bouros, Nikos Mamoulis, Dimitrios Tsitsigkos, and Manolis Terrovitis. 2021. In-Memory Interval Joins. VLDB J. 30, 4 (2021), 667–691.
[12]
Francesco Cafagna and Michael H. Böhlen. 2017. Disjoint interval partitioning. VLDB J. 26, 3 (2017), 447–466.
[13]
Matteo Ceccarello, Anton Dignös, Johann Gamper, and Christina Khnaisser. 2022. Indexing Temporal Relations for Range-Duration Queries. CoRR abs/2206.07428 (2022). https://doi.org/10.48550/arXiv.2206.07428
[14]
George Christodoulou, Panagiotis Bouros, and Nikos Mamoulis. 2022. HINT: A Hierarchical Index for Intervals in Main Memory. In SIGMOD. ACM, 1257–1270.
[15]
Anton Dignös, Michael H. Böhlen, and Johann Gamper. 2014. Overlap interval partition join. In SIGMOD. ACM, 1459–1470.
[16]
Anton Dignös, Michael H. Böhlen, Johann Gamper, and Christian S. Jensen. 2016. Extending the Kernel of a Relational DBMS with Comprehensive Support for Sequenced Temporal Queries. ACM Trans. Database Syst. 41, 4 (2016), 26:1–26:46.
[17]
Anton Dignös, Michael H. Böhlen, Johann Gamper, Christian S. Jensen, and Peter Moser. 2022. Leveraging range joins for the computation of overlap joins. VLDB J. 31, 1 (2022), 75–99.
[18]
Jialin Ding, Vikram Nathan, Mohammad Alizadeh, and Tim Kraska. 2020. Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads. CoRR abs/2006.13282 (2020).
[19]
Herbert Edelsbrunner. 1980. Dynamic Rectangle Intersection Searching. Technical Report 47. Institute for Information Processing, TU Graz, Austria.
[20]
Raphael A. Finkel and Jon Louis Bentley. 1974. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica 4 (1974), 1–9.
[21]
Y. Hayashi and D. L. Paterson. 2011. Strategies for Reduction in Duration of Antibiotic Use in Hospitalized Patients. Clinical Infectious Diseases 52, 10 (April 2011), 1232–1240.
[22]
Alistair E W Johnson, Tom J Pollard, Lu Shen, Li-Wei H Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. 2016. MIMIC-III, a freely accessible critical care database. Scientific data 3, 1 (2016), 1–9.
[23]
Martin Kaufmann. 2013. Storing and Processing Temporal Data in a Main Memory Column Store. Proc. VLDB Endow. 6, 12 (2013), 1444–1449.
[24]
Martin Kaufmann, Amin Amiri Manjili, Panagiotis Vagenas, Peter M. Fischer, Donald Kossmann, Franz Färber, and Norman May. 2013. Timeline index: a unified data structure for processing queries on temporal data in SAP HANA. In SIGMOD. ACM, 1173–1184.
[25]
Nick Kline and Richard T. Snodgrass. 1995. Computing Temporal Aggregates. In ICDE. IEEE Computer Society, 222–231.
[26]
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In SIGMOD. ACM, 489–504.
[27]
Hans-Peter Kriegel, Marco Pötke, and Thomas Seidl. 2000. Managing Intervals Efficiently in Object-Relational Databases. In VLDB. 407–418.
[28]
Hans-Peter Kriegel, Erich Schubert, and Arthur Zimek. 2017. The (black) art of runtime evaluation: Are we comparing algorithms or implementations?Knowl. Inf. Syst. 52, 2 (2017), 341–378.
[29]
Krishna G. Kulkarni and Jan-Eike Michels. 2012. Temporal features in SQL: 2011. SIGMOD Rec. 41, 3 (2012), 34–43.
[30]
D. G. Joakim Larsson and Carl-Fredrik Flach. 2022. Antibiotic resistance in the environment. Nature Reviews Microbiology (Nov. 2022), 257–269.
[31]
Bongki Moon, Inés Fernando Vega López, and Vijaykumar Immanuel. 2003. Efficient Algorithms for Large-Scale Temporal Aggregation. IEEE Trans. Knowl. Data Eng. 15, 3 (2003), 744–759.
[32]
Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim Kraska. 2020. Learning Multi-Dimensional Indexes. In SIGMOD. ACM, 985–1000.
[33]
Jürg Nievergelt, Hans Hinterberger, and Kenneth C. Sevcik. 1984. The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9, 1 (1984), 38–71.
[34]
Fabio Persia, Fabio Bettini, and Sven Helmer. 2017. An Interactive Framework for Video Surveillance Event Detection and Modeling. In CIKM. ACM, 2515–2518.
[35]
Danila Piatov and Sven Helmer. 2017. Sweeping-Based Temporal Aggregation. In SSTD(LNCS, Vol. 10411). Springer, 125–144.
[36]
Danila Piatov, Sven Helmer, and Anton Dignös. 2016. An interval join optimized for modern hardware. In ICDE. IEEE Computer Society, 1098–1109.
[37]
Danila Piatov, Sven Helmer, Anton Dignös, and Fabio Persia. 2021. Cache-efficient sweeping-based interval joins for extended Allen relation predicates. VLDB J. 30, 3 (2021), 379–402.
[38]
Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Morgan Kaufmann.
[39]
Gereon Schüller, Andreas Behrend, and Rainer Manthey. 2010. AIMS: an SQL-based system for airspace monitoring. In GIS-IWGS. ACM, 31–38.
[40]
Gereon Schüller, Philip Schmiegelt, and Andreas Behrend. 2012. Supporting Phase Management in Stream Applications. In ADBIS(LNCS, Vol. 7503). Springer, 332–345.
[41]
Daniel J. Shapiro, Matthew Hall, Susan C. Lipsett, Adam L. Hersh, Lilliam Ambroggio, Samir S. Shah, Thomas V. Brogan, Jeffrey S. Gerber, Derek J. Williams, Carlos G. Grijalva, Anne J. Blaschke, and Mark I. Neuman. 2021. Short- Versus Prolonged-Duration Antibiotics for Outpatient Pneumonia in Children. The Journal of Pediatrics 234 (July 2021), 205–211.e1.
[42]
Thatcher Ulrich. 2000. Loose Octrees. In Game Programming Gems. Charles River Media, 444–453.
Index Terms
- Indexing Temporal Relations for Range-Duration Queries
Recommendations
Indexing range sum queries in spatio-temporal databases
Although spatio-temporal databases have received considerable attention recently, there has been little work on processing range sum queries on the historical records of moving objects despite their importance. Since the direct access to a huge amount ...
Containment of conjunctive queries on annotated relations
ICDT '09: Proceedings of the 12th International Conference on Database TheoryWe study containment and equivalence of (unions of) conjunctive queries on relations annotated with elements of a commutative semiring. Such relations and the semantics of positive relational queries on them were introduced in a recent paper as a ...
Containment of Conjunctive Queries on Annotated Relations
We study containment and equivalence of (unions of) conjunctive queries on relations annotated with elements of a commutative semiring. Such relations and the semantics of positive relational queries on them were introduced in a recent paper as a ...
Comments
Information & Contributors
Information
Published In
July 2023
232 pages
ISBN:9798400707469
DOI:10.1145/3603719
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 August 2023
Check for updates
Badges
Best Paper
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SSDBM 2023
SSDBM 2023: 35th International Conference on Scientific and Statistical Database Management
July 10 - 12, 2023
CA, Los Angeles, USA
Acceptance Rates
Overall Acceptance Rate 56 of 146 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 320Total Downloads
- Downloads (Last 12 months)278
- Downloads (Last 6 weeks)23
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in