The management of intervals has been an active research area since databases were invented. A popular direction of research is the indexing and retrieval of intervals, finding a wide range of applications. Emerging and widely used systems are built dependent on temporal and uncertain data. Many algorithms and indices have been proposed, concentrated on a variety of queries. Most algorithms are either suboptimal in space consumption or perform well only for specific query types. We need novel and eficient in-memory indices for intervals, which can execute queries with high performance. In this PhD research, we aim to explore partitioning approaches, which are versatile, have low space requirements and provide high query performance.
Published in the Workshop Proceedings of the EDBT/ICDT 2023 Joint Conference (March 28-March 31, 2023, Ioannina, Greece) $ gchristodoulou@cse.uoi.gr (G. Christodoulou) © 2023 Copyright for this paper by its authors. Use permitted under solutions which take advantage of modern hardware Creative Commons License Attribution 4.0 International (CC BY such as multi-core systems and large main memories, CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g 4C.0E).UR Workshop Proceedings (CEUR-WS.org) can handle traditional and on demand indexing of tree for disk-resident data was proposed in [7]. intervals, and provide high performance for a wide
variety of query types and predicates. advent of temporal databases [2]. A number of in
The rest of the report is organized as follows. dices are proposed for secondary memory, mainly
for efective versioning and compression [ 11, 12]. for intervals, for diefrent types of interval queries.
the problem of interval data management.
section presents the state-of-the-art on areas related to this research, including data structures for interval data, algorithms for temporal aggregation and algorithms for interval joins.
A simple and practical data structure for intervals is a 1D-grid, which divides the domain into pairwise disjoint partitions. Each interval is assigned to all partitions that it overlaps with. Given a range query , the results can be obtained by accessing each partition that overlaps with . If the interval of a range query overlaps with multiple partitions, duplicate results may be produced. Thus, duplicate elimination is needed. Finally, if the collection conat certain timestamps, checkpoints are kept with the alive intervals. The evaluation of some query types in the Timeline Index are suboptimal. The index also requires a lot of extra space to store the active sets of the checkpoints. The timeline index can be directly used for temporal aggregation. Piatov et al. [20] present a collection of plane-sweep algorithms that extend the timeline index to support aggregation over fixed intervals, sliding window aggregates, and MIN/MAX aggregates. The timeline index was later adapted for interval overlap joins [16]. A domain partitioning technique for parallel processing of interval joins was proposed in [17]. Additional research on indexing intervals addresses operations such as temporal aggregation [13, 14] and interval joins [15, 16, 17, 18, 19].
tains many long intervals, the index may grow large In this section, we show the body of work that has in size due to excessive replication.
been done or is currently the focus of this PhD
ing only necessary information for each interval. each of them is divided hierarchically to levels. Each Also, evaluating diferent query types with the minlevel corresponds to a duration length and each in- imum amount of comparisons needed in order to terval is assigned to the level corresponding to its minimize the computational cost. only at the levels which are inside the query dura- cal index (HINT) with binary representations of duration. During query evaluation, only the divisions that overlap the query range are accessed and tion limits. The main drawback of this approach is that the hierarchy of duration sizes helps only at the upper levels. At the bottom level, an interval can expand through the whole domain and thus be stored into every partition it overlaps.
One of the most popular data structures for in- illustrates the hierarchical domain partitioning for tervals is Edelsbrunner’s interval tree [6]. The tree divides the domain hierarchically and places intervals recursively at the first node they overlap. The intervals assigned to each node are sorted in two lists based on their starting and ending values, respectively. Interval trees are used to answer stabbing backs are the redundant comparisons needed for and interval (i.e., range) queries. The main draw- level ℓ = 3. the query result and the unnecessary visits of nodes which may not contain results. A relational interval = 4.
smallest set of partitions from all levels which collectively define . We assign longer interval parts in higher levels so that we avoid extensive replication.
to one partition at level ℓ = 4 and two partitions at
The number of bits
is critical for the performance of our index. We can model our data collection with
equal to the number of bits needed for is Hierarchical Index For Selection Queries
The basic idea introduced in [21], is a hierarchiintervals. A regular hierarchical decomposition of the domain into partitions is defined, where at each level ℓ from 0 to , there are 2
ℓ partitions. The number of bits used for the interval representations and therefore
+ 1 levels are created. Figure 1 P2,0
P1,0 0
P0,0 0 P2,1 01
P2,2 10
P1,1 1
P2,3 Hierarchical partitioning of space
Range queries
P0,0 P1,0
P1,1 P3,0 P3,1 P3,2 P3,3 P3,4 P3,5 P3,6 P3,7
011 100 P4,0 P4,1 P4,2 P4,3 P4,4 P4,5 P4,6 P4,7 P4,8 P4,9 P4,10P4,11 P4,12 P4,13 P4,14P4,15 0101 representing the biggest endpoint in the collection. order of magnitude in a wide variety of data and In this case, intervals are assigned to partitions query distributions. which they completely cover. When evaluating a Queries With Allen’s Predicates range query, each relevant partition contains inter- Currently, we focus on the performance of our vals which surely overlap with the query interval. index on more specific queries. Intervals may satisfy Thus, there is no need for comparisons, and without more sophisticated relations, which are based on comparisons there is also no need for storing the Allen’s relationships [22](e.g., find all intervals that endpoints of intervals. So, for each interval we keep are covered by the query interval). The principles of only an identifier. The drawback of this approach HINT are useful for the retrieval of data intervals is the space requirement for covering large domains. based on Allen’s relationships. The hierarchical par
We can reduce memory consumption by using a titioning applies independently of the query type. smaller and rescale all the intervals using only Although, multiple challenges arise by this functhe prefix with the most significant bits of their tionality extension on HINT. The main challenge is binary representations. The query intervals are also to optimize the index for all the query predicates, rescaled using the same amount of bits. In that which access diferently the relevant partitions. Anway, fewer levels are created but we may need to other challenge emerges from the increased inforperform comparisons at the first partition and the mation we need to keep for each interval, because last partition of each level that the query interval diferent endpoints are useful for answering diferent overlaps. This holds because the intervals do not query predicates. Our index is evaluated against the necessarily contain the whole partition that they state-of-the-art solutions with multiple real datasets. are assigned to, as before, because of rescaling. Al- Our first experiments show a small increase in storthough, comparisons can be avoided after a certain age consumption but also a consistent lead in query level. For the range query evaluation, we need to throughput. ifnd partitions that overlap with at each level.
The division of intervals in each partition into groups, originals and replicas , helps avoid- 4. Future Work ing the production of duplicate query results and minimizes the number of intervals that have to be For future work, there are several directions. First, accessed in each query. For example, in Figure 2 we plan to investigate extensions of our index that we can see the accessed partitions for the query in- could support queries that combine temporal selecterval [5, 9]. The binary representations of . and tions and selections on additional object attributes . are 0101 and 1001, respectively. The relevant (e.g., find all people employed during February 2021, partitions at each level are shown in bold (blue) and whose wages were at least $5000). dashed (red) lines and can be determined by the Indexing Temporal Data. Our envisioned method corresponding prefixes of 0101 and 1001. At each will be based on HINT with an adaptation of temlevel, we report both originals and replicas in the poral data specifics. Indexing temporal data diferifrst partitions while in the subsequent partitions, entiates from indexing a known collection of data, we report only the original intervals, so we avoid mainly because data evolve. The index will handle duplicate results. closed time intervals, but multiple objects may have
We evaluated our method against state-of-the-art alive time intervals. These time intervals will be indices. HINT has low space complexity and mini- inserted in the lowest level, but will end up in parmizes the number of data accesses and comparisons titions of higher levels. Furthermore, the number during query evaluation. Our experimental analysis of bits/levels used for the interval representations shows that HINT outperforms previous work by one will be dependent of the time granularity of the database and needs separate investigation for an [7] H. Kriegel, M. Pötke, T. Seidl, Managing interoptimal setup. vals eficiently in object-relational databases, Multiple Temporal Operators. Most proposed in- in: VLDB, 2000, pp. 407–418. dices are specialized on one temporal operator. [8] M. Kaufmann, A. A. Manjili, P. Vagenas, P. M. Keeping a diferent index for each type of query Fischer, D. Kossmann, F. Färber, N. May, is not afordable for a DBMS in terms of tuning, Timeline index: a unified data structure for maintenance and storage overhead. Diferent indices processing queries on temporal data in SAP will have diferent beneficial sortings, will possibly HANA, in: ACM SIGMOD, 2013, pp. 1173– cause data replication and diferent optimizations in 1184. general. All the commonly used operators, temporal [9] A. Behrend, A. Dignös, J. Gamper, aggregation, time travel and temporal join should P. Schmiegelt, H. Voigt, M. Rottmann, be supported by one index. Eventually, we want K. Kahl, Period index: A learned 2d hash to create a versatile index for answering diferent index for range and duration queries, in: types of queries and capable of temporal database SSTD, 2019, pp. 100–109. system integration. [10] M. de Berg, O. Cheong, M. J. van Kreveld, M. H. Overmars, Computational geomAdditional Attributes. Another challenge consists in etry: algorithms and applications, 3rd Edition, managing dimensions added from additional object Springer, 2008. attributes. Other attributes may lead to diferent [11] B. Becker, S. Gschwind, T. Ohler, B. Seeger, query evaluation strategies, diferent optimization P. Widmayer, An asymptotically optimal multechniques or even specific indexing/sorting that tiversion b-tree, VLDB J. 5 (1996) 264–275. will improve throughput and storage consumption. [12] D. B. Lomet, M. Hong, R. V. Nehme, R. Zhang, Distributed Computation. Moreover, the data may Transaction time indexing with version combe distributed among multiple physical locations. pression, Proc. VLDB Endow. 1 (2008) 870– Splitting the data must be done eficiently, with low 881. storage consumption and the query algorithm will [13] N. Kline, R. T. Snodgrass, Computing temcontain multiple tasks contributing to the result. poral aggregates, in: IEEE ICDE, 1995, pp. In each single node, the tasks will be assigned to 222–231. diferent cores for parallel processing of the queries. [14] B. Moon, I. F. V. López, V. Immanuel, EfiAcknowledgments cient algorithms for large-scale temporal aggregation, IEEE TKDE 15 (2003) 744–759.
Partially supported by Greek national funds, under [15] A. Dignös, M. H. Böhlen, J. Gamper, Overlap the Research-Create-Innovate call (project T2EDK- interval partition join, in: ACM SIGMOD, 02848). 2014, pp. 1459–1470. [16] D. Piatov, S. Helmer, A. Dignös, An interval References join optimized for modern hardware, in: IEEE ICDE, 2016, pp. 1098–1109. [1] R. T. Snodgrass, I. Ahn, Temporal databases, [17] P. Bouros, N. Mamoulis, A forward scan based
Computer 19 (1986) 35–42. plane sweep algorithm for parallel interval joins, [2] M. H. Böhlen, A. Dignös, J. Gamper, C. S. Proc. VLDB Endow. 10 (2017) 1346–1357.
Jensen, Temporal data management - an [18] D. Piatov, S. Helmer, A. Dignös, F. Persia, overview, in: eBISS, 2017, pp. 51–83. Cache-eficient sweeping-based interval joins [3] N. N. Dalvi, D. Suciu, Eficient query evalu- for extended allen relation predicates, VLDB ation on probabilistic databases, in: VLDB, J. 30 (2021) 379–402.
2004, pp. 864–875. [19] F. Cafagna, M. H. Böhlen, Disjoint interval [4] P. Samarati, L. Sweeney, Generalizing data to partitioning, VLDB J. 26 (2017) 447–466. provide anonymity when disclosing information [20] D. Piatov, S. Helmer, Sweeping-based tempo(abstract), in: ACM PODS, 1998, p. 188. ral aggregation, in: SSTD, 2017, pp. 125–144. [5] J. Min, M. Park, C. Chung, XPRESS: A que- [21] G. Christodoulou, P. Bouros, N. Mamoulis, riable compression for XML data, in: ACM HINT: A hierarchical index for intervals in SIGMOD, 2003, pp. 122–133. main memory, in: ACM SIGMOD, 2022, p. [6] H. Edelsbrunner, Dynamic Rectangle Intersec- 1257–1270.
tion Searching, Technical Report 47, Institute [22] J. F. Allen, An interval-based representation for Information Processing, Technical Univer- of temporal knowledge, in: IJCAI, 1981, pp. sity of Graz, Austria, 1980. 221–226.