Manuscript of arXiv
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
arXiv:2606.22773v1 [cs.DB] 22 Jun 2026
Kai Wang · Moin Hussian Moti · Dimitris Papadias
Received: date / Accepted: date
Abstract Indexes for large collections of intervals are common in temporal databases, where each record has a lifespan, or validity interval. Despite their conceptual differences, we demonstrate that interval indexes can be captured by some corner structure in a 2D space. This representation facilitates the optimization of query processing by identifying nodes that must contain query results versus nodes that may contain results. In addition, we explore the assumption that intervals arrive in order of increasing ending time (IET) to develop disk-based indexes that have compact size, efficient insertions, and fast query processing. Specifically, we first develop CEB, an index in the corner space defined by the interval center and endpoint. Our second contribution is TIDE, which organizes intervals by their duration and endpoint. CEB and TIDE adopt a two-layer architecture, where the leaf nodes of a top tree (ordering intervals by their center or duration) correspond to the root nodes of bottom trees, ordering intervals by their endpoints. Both top and bottom trees are append-only B+-trees to facilitate fast insertions. CEB and TIDE outperform state-of-the-art competitors in terms of index size and insertion speed. In addition, TIDE is always faster in query processing, sometimes by orders of magnitude.
1 Introduction In temporal databases each record has a lifespan, or validity interval [ts ,te ), where ts < te . A record is considered alive if te equals the current time (now); otherwise, it is dead. The most important queries on intervals are stabbing and range queries, which retrieve all intervals intersecting a timestamp or period in history. These query types form the basic building blocks of more complex tasks. Their efficient processing necessitates interval indexes, which depending on the application requirements, can be disk or main-memory based. They can also be classified as static, if they assume that all data intervals are known in advance, or dynamic if they allow insertions of new intervals. Dynamic indexes are partially persistent [15, 31], if updates can only occur at the current time. Consequently, nodes storing dead intervals are immutable. On the other hand, fully persistent [27, 8] structures allow updates at any point in the past.
M. Hussian Moti Department of Computer Science and Engineering, HKUST, Clearwater Bay, Hong Kong E-mail: [email protected]
We demonstrate that interval indexes can be captured by some corner structure in a 2D space, defined by selecting two out of four possible dimensions including starting time ts , ending time te , duration d, and center point c. This unified representation facilitates the optimization of query processing by identifying nodes that must contain query results (i.e., all their intervals can be directly reported) versus nodes that may contain results (i.e., their intervals must be examined individually). Moreover, the representation provides useful insight into the advantages and shortcomings of each index. Specifically, some structures have highly unbalanced nodes, while others involve redundancy, which necessitates duplicate elimination during query processing.
D. Papadias Department of Computer Science and Engineering, HKUST, Clearwater Bay, Hong Kong E-mail: [email protected]
In this paper, we focus on disk-based interval indexes, assuming that intervals arrive in increasing order of their ending time te , i.e., they are added to the database when they
Keywords Intervals · Temporal Indexes K. Wang Department of Computer Science and Engineering, HKUST, Clearwater Bay, Hong Kong E-mail: [email protected]
2
Kai Wang et al.
die. In addition to being realistic 1 , this Increasing Ending Time (IET) assumption yields a form of partial persistence that has significant advantages on the index properties: (i) it leads to the existence of immutable nodes that are full (or can be compressed), thus minimizing the total index size; (ii) it enables append-only insertions, which are very fast. The only other index aimed at IET is SEB [35], which is based on a corner structure defined by ts and te . SEB includes a twolevel scheme: a top B+-tree indexes ts , while intervals with similar values of ts are grouped together in bottom B+-trees ordered by te . New intervals can only be appended to the last node of the bottom tree that covers the corresponding ts , and the rest of the nodes are immutable. The main problem of SEB is the existence of numerous (thousands or millions depending on the dataset) bottom trees, each with a mutable last node, which affects negatively insertion and query performance. To mitigate this issue, we first propose CEB (Center and Endpoint B-tree), which aims at improving SEB by decreasing the number of mutable nodes. CEB also consists of two layers of appendonly B+-trees. The top-tree is ordered by the center point e (c = ts +t 2 ) of intervals. The leaf nodes of the top tree correspond to the root nodes of bottom trees, which are B+-trees ordered by te . The advantage of CEB compared to SEB is that the bottom trees with maximum c below now 2 will never receive insertions, and can be compressed to immutable full nodes. Although CEB indeed reduces the bottom trees compared to SEB, their number continuously grows with time because c, similar to ts , is ever increasing. The only interval property (among ts , te , c, and d) that does not necessarily grow with time is the duration d. This observation led to our second contribution TIDE (Time Intervals by Duration and Endpoint), where the top tree organizes intervals by d, and the bottom trees by te . This yields a very small number of bottom trees, especially for datasets that involve low duration variance. Although in TIDE, the last node of each bottom tree is mutable, the total number of mutable nodes is much lower than SEB and CEB, facilitating high compactness and cache locality. We evaluated CEB and TIDE against SEB [35] and the RI-tree [26], the state-of-the-art disk-based interval index, using real datasets with diverse characteristics. CEB and SEB have, in general, similar overall cost, and both outperform the RI-tree on insertion performance and index size. On the other hand, the RI-tree is faster on query processing. TIDE is always the fastest on every aspect, often outperforming the rest by orders of magnitude. Moreover, it achieves better 1
IET can be utilized even for applications where the intervals arrive in a different order, e.g., ts . In this case alive intervals can be maintained by a main-memory index on ts and, when they die, they are moved to the disk-based index on te . In practice, since alive intervals are usually a small fraction of the dead ones, it is reasonable to maintain them in memory.
10 13
(a) interval-tree
(b) segment-tree
Fig. 1: Classical structures
space efficiency because its insertion strategy generates full nodes. The rest of the paper is organized as follows. Section 2 reviews existing interval indexes. Section 3 describes a representation that enables optimization of query processing and conceptual evaluation of different indexes under a unifying framework. Section 4 and Section 5 present the insertion and query processing algorithms of CEB and TIDE, respectively. Section 6 compares TIDE and CEB against SEB and the RI-tree under different metrics and datasets, and Section 7 concludes the paper.
2 Related work Section 2.1 focuses on main-memory, and Section 2.2 on disk-based interval indexes.
2.1 Main-memory interval indexes In the interval-tree [16], intervals are first sorted on their endpoints, and are then organized in a binary search tree BST. Figure 1a shows the BST for 13 intervals s0 , ..., s12 , in increasing ending time. The top node n14 corresponds to median endpoint at time 14. An interval is stored at the highest overlapping node of BST; e.g., s8 , s11 are stored at n25 . In each BST node, the stored intervals are duplicated in two sorted lists: ascending order of ts , and descending order of te . Assume for instance, a range query [10,13] in Figure 1a. All intervals assigned to BST nodes n12 , n13 within [10,13] qualify the query. In addition, some nodes on either side of the range (n6 , n9 , n14 ) may contain results. Specifically, for BST nodes n6 , n9 before [10,13], we scan the te list (descending order) and report all intervals, until reaching the first one with te < 10. For BST node n14 after [10,13], we scan the ts list (ascending order) and report all intervals, until reaching the first one with ts > 13. No other BST nodes, may contribute results. Interval-tree nodes may be very unbalanced. For example, in Figure 1a, the root node n14 contains numerous intervals (s4 , s5 , s6 , s7 , s9 , s10 ), while several BST nodes, e.g., n1 , n2 , n12 , are empty. To avoid this issue, the segment-tree [5]
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
0
4
8
12
16
20
24
28
32
Fig. 2: Period-index
0
2
4
6
8
3
interval in HINT is marked as original, and the rest are replicas. During query processing, for all partitions intersecting the start of the query range, all data intervals are examined. For the remaining partitions, only originals may constitute results (replicas correspond to duplicates). LIT [11] extends HINT for dynamic intervals. The RD-tree [9] has two variants: RD-tree-td, sorts intervals by ts and duration d; RDtree-dt, sorts intervals by d and ts . Finally, interval indexes have been applied for specialized tasks including temporal aggregation [36], interval sampling [1] and interval joins [6, 7, 23].
10 12 14 16 18 20 22 24 26 28 30 32
Fig. 3: HINT
partitions and stores each interval in multiple nodes. Specifically, an interval is first stored at all leaf nodes that intersect it. Then, consecutive partitions are merged at the upper level recursively, if they fully cover their parent node. For example, in Figure 1b, interval s7 = [2, 23) is stored in n4 , n12 , n18 and nL23 , where L (R) denotes left (right) leaf node. Due to replication, the segment-tree consumes O(N log N) space, where N is the interval cardinality. Range query processing requires duplicate elimination since the same interval may exist in several nodes, possibly at different levels. A learned period-index [4] splits the time domain into temporal periods (e.g., days) and divides each period hierarchically. Figure 2 shows thirteen intervals in two periods p0 and p1 . Each period has length l = 16 and is partitioned into h = 3 levels. Both l and h are learned parameters. An interval is stored at the top level such that its duration is more than half of the extent of that level. For example, s2 = [3, 9) is assigned to L1 because its length (6) exceeds half the length of level 1. Since s2 intersects two partitions of L1 , it is stored in both. A range query searches all levels intersecting its range. Compared to the segment-tree, the period-index incurs less redundancy (because all copies of an interval are at the same level), but duplicate elimination is still necessary for range queries. HINT [10] also applies a hierarchical decomposition of buckets into h levels. In Figure 3, there are h = 5 levels: the top L0 covers the entire domain, while each bucket in L4 covers two timestamps. An interval is first stored at all bottom level partitions that intersect it. Then, consecutive partitions with the same parent are merged at the upper level recursively, if they partially intersect (as opposed to be fully covered as in the segment-tree). For instance, s7 = [2, 23) is stored with only two duplicates (i.e., s7−1 in level L1 and s7−2 in level L2 ), while the segment-tree requires four (see Figure 1b). In other cases (e.g., s2 , s12 ), both indexes have the same number of duplicates. The first occurrence of an
Method
Domain
Partitioning
#Copies/Interval
interval-tree [16]
fixed
data-driven
2
segment-tree [5]
fixed
data-driven
≤ 2 · log2 N
period-index [4]
growing
space-driven
≤ max(2, nb )
HINT [10]
fixed
space-driven
≤ 2·h
RD-tree [9]
fixed
data-driven
1
* nb is the number of buckets in the period-index. * h is the number of levels in HINT.
Table 1: Summary of in-memory interval indexes
Table 1 summarizes the properties of in-memory interval indexes. Most indexes assume static intervals over a fixed domain, and are not suitable for ever-evolving time. Though the period-index assumes a growing temporal domain, it requires a fixed period length, determined in advance. Indexes can also be classified as space-driven (or data-driven), if they partition the temporal domain using regular ranges/grids (or based on the data intervals). Finally, most in-memory interval indexes incur redundancy (i.e., they store each interval more than once), requiring some form of duplicate elimination during query processing.
2.2 Disk-resident interval indexes The external interval-tree (EI-tree) and external segmenttree (ES-tree) [2] are disk-based extensions of their mainmemory counterparts that √ replace the binary search tree (BST) with a B+-tree of fanout B, where B is the disk page capacity. Similar to the in-memory structures, they maintain two sorted lists (with unlimited capacity) per B+-tree node, which may lead to expensive updates. For example, a split would force numerous intervals to move between nodes. To decrease the update cost, the EI-tree and ES-tree use complicated buffer tree and weight balancing techniques, which are theoretical in nature. The time-index [17] stores alive records at the first timestamp of each node, and incremental updates at the following
4
Kai Wang et al.
10
13
(a) Decomposition
(b) Leaf pages of two B+-trees
Fig. 4: Relational interval-tree timestamps. The append only-tree (AP-tree) [33] orders intervals by their starting time ts using an append-only B+tree. The AP-tree has optimal insertion speed, but is slow to answer stabbing queries. Another trend extends R-tree and its variants [34, 3] to manage intervals. However, R-trees are not effective for long intervals and high overlaps [26]. To deal with long intervals, the segment R-tree (SR-tree) [25] combines the main-memory segment-tree with the diskbased R-tree. Similar to the segment-tree, intervals in the SR-tree are stored in both leaf and internal nodes, leading to redundancy. Therefore, it consumes O( NB logB N) space [31]. The relational interval-tree (RI-tree) [26] assumes the domain to be a range (0, 2h ), where h denotes the minimum integer that fulfills 2h > now. Similar to HINT, it maintains a hierarchical decomposition with h levels. The partitioning is space-driven, and remains valid until now ≥ 2h , in which case h increases by 1 to expand the domain. For instance, Figure 4a shows a decomposition with height h = 5 and now = 30, assuming the same intervals as Figure 1a. Its root bucket b16 corresponds to the middle of 2h = 32 and leaf nodes (e.g., b1 , b3 ) to individual timestamps. As shown in Figure 4b, the RI-tree maintains two B+-trees, Bs ,Be , ordering intervals by composite key (bucket,ts ) and (bucket,te ), respectively. An interval is assigned to the highest overlapped bucket and inserted into both B+-trees. For instance, s0 = [1, 6) is assigned to b4 , and an entry < b4 , 1, s0 > (< b4 , 6, s0 >) is inserted to Bs (Be ). Figure 4b shows the leaf nodes of Bs ,Be assuming that disk page capacity is 3. Observe that (i) each interval is stored once per tree, (ii) the occurrences of a bucket per tree equals the number of assigned intervals, and (iii) a bucket may be stored in multiple consecutive pages. Given a range query of [10, 13], processing starts from the root bucket b16 . Since b16 is after the range, the first entry for b16 (i.e., < b16 , 1, s10 > in Figure 4b) is found at Bs ; s10 and all subsequent intervals (e.g., s7 , s6 , s4 , s9 ) until the first with ts > 13 (s5 ), are returned as results. At the next level, b24 cannot contain results because all its intervals must start after b16 . On the other hand, b8 may contain intervals that start before timestamp 8 and finish before 16. To retrieve these results, we locate b8 at Be and output all its intervals that end after time 10 (s3 ). 2 Bucket b12 could potentially 2
Each intersected bucket bi requires a range query, either from < bi , −∞ > to < bi , 13 > in Bs , or from < bi , 10 > to < bi , +∞ > in Be .
28
28
24
24
20
20
16
16
12
12
8
8
4 0
4
4
8
12
16
20
24
(a) stabbing query
28
32
0
4
8
12
16
20
24
28
32
(b) range query
Fig. 5: Diagonal corner queries
contain results, but it is empty. The lowest two levels are not searched, because the RI-tree records the deepest level that receives insertions (and all buckets at these levels are empty). [24] maps intervals to a 2-dimensional (2D) space, where ts is the horizontal and te is the vertical axis. The mapped points lie above line te = ts , because te > ts , forming a diagonal corner structure 3 . For example, in Figure 5a, a stabbing query at time 20 retrieves all points (intervals) in the shaded area. In Figure 5b, a query with range [10, 13] returns points with ts ≤ 13 and te ≥ 10. Early work on corner structures has been of theoretical nature, assuming static data [31, 37]. Space-partitioning Generalized search trees (SPGiST4 ) [18] maintain points in corner spaces using spatial indexes such as KD-trees or R-trees in PostgreSQL. Following a similar idea, TDSQL manages mapped points with Rtree variants [28]. DOT [19] indexes points in corner spaces by a B+-tree after applying space-filling curves (e.g., Peano or Hilbert) to generate 1D order. The above approaches assumed that mapped points are uniformly distributed, but it was later shown that corner spaces are usually skewed [20], exhibiting higher density near the diagonal te = ts . The interval spatial transformation (IST) [21] maps intervals into a 2D space of ts (x-axis) and d (y-axis), where d is the duration. IST forms a triangle starting from point (0, 0) and bounded by line te = ts + d ≤ now. The points are sorted and indexed by a single B+-tree. Depending on the ordering, there are three variants: D(iagonal) (sort by te ,ts ), V(ertical) (sort by ts ,te ), and H(orizontal) (sort by d,ts ). Figure 6a shows D-ordering, assuming a B+-tree node capacity of 3. The first node contains the three intervals closest to (0, 0) with the smallest te . Figure 6b shows an example of H-ordering, where the first node of B+-tree contains the three intervals with the shortest duration. Instead of end3 We use the terms corner structure and corner space interchangeably. 4 https://github.com/postgres/postgres/blob/REL_10_ STABLE/src/backend/utils/adt/rangetypes_spgist.c
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
5
28
28
28
24
24
24
20
20
20
16
16
16
12
12
12
8
8
8
4
4
0
4
8
12
16
20
24
28
B+ tree
4
0
4
8
12
16
20
24
28
0
4
8
12
16
20
24
28
0
(a) D-ordering by te ,ts
(b) H-ordering by d,ts
(a) the structure
(b) range query
Fig. 6: Interval spatial transformation
Fig. 8: SEB
points, midpoint transformation [29, 32] maps interval cente −ts e ters ts +t 2 (x-axis) and expansions 2 (y-axis). Figure 7a shows the mapped space, which is bounded by ts = x − y ≥ 0 and te = x + y ≤ now. Midpoint transformations are limited to theoretical interest due to potentially complicated queries [20]. For instance, as shown in Figure 7b, a range query [10, 13] returning points with ts ≤ 13 and te ≥ 10 has a complex shape and boundaries.
SEB uses a top-layer B+-tree to index the columns, which correspond to nodes with the same ts range, as shown in Figure 8b. Each column is indexed by a separate B+-tree, called a bottom tree (BT). An insertion of new interval [ts ,te ) first locates the bottom tree that corresponds to ts . Given the IET assumption, point (ts ,te ) is appended to the last node of that BT. A range query [qs , qe ] identifies column i (and j) covering qs (and qe ). All nodes in columns up to j are examined for results, provided that their te exceeds qs . SEB has been used mostly for trajectory management [13, 30, 14]. The compressed start end-tree [38] applies similar concepts, but switches the order from < ts ,te > to < te ,ts >. This however introduces high update cost because insertions may occur at any node (as opposed to the last node of some column as in SEB). Table 2 summarizes the practical disk-resident interval indexes, including the corresponding structure in the last column. Most methods assume a growing time domain, excluding SP-GiST [18] and DOT [19]), which require nontrivial extensions. The RI-tree and DOT are space-driven, whereas the rest are data-driven. Except for the RI-tree that stores each interval twice, the rest have no redundancy. Only the SEB utilizes IET, allowing for efficient append-only insertions. In the RI-tree and IST insertions may happen at any node, which may lead to numerous nodes that are below capacity.
16
16
12
12
8
8
4 0
4
4
8
12
16
20
24
28
32
(a) the structure
0
4
8
12
16
20
24
28
32
(b) query with range [10, 13]
Fig. 7: Midpoint transformation
The start/end timestamp B-tree (SEB) [35] applies corner structures for indexing intervals following the IET assumption: intervals are inserted in increasing order of te . Figure 8a shows SEB for thirteen intervals in six data nodes with capacity 3. Initially, there is a single data node D0 that covers the entire diagonal corner space, ts ∈ [0, +∞) and te ∈ (0, +∞). When D0 overflows at time 9, it generates two nodes D1 and D2 . D1 is the first node in its column with a new ts range (4, +∞). D2 is a node with the same ts range as D0 [0, 4], and a different te range [9, +∞). D0 is full and becomes immutable. D1 and D2 are non-full and ready to accept insertions. A new point always falls into D1 (if its ts > 4) or D2 (if ts ≤ 4). When a non-first node overflows, it only requires horizontal partitioning. For example, at time 27, the overflow of D2 creates node D5 with the same ts range [0, 4] as D2 . Points in D2 fulfill te ∈ [9, 27], while points in D5 have te ∈ [27, +∞).
3 Corner Structures for Interval Indexes In this section, we demonstrate that interval indexes, in general, can be captured by some corner structure in a 2D space, defined by the endpoints ts , te , duration d, or center point c. This representation enables the identification of nodes that must contain query results (i.e., all their intervals can be directly reported) versus nodes that may contain results (i.e., their intervals must be individually examined). In addition to reducing the computation cost of regular queries, this may also decrease the I/O cost of aggregate queries. For instance,
6
Kai Wang et al. Method
Domain
Partitioning
#Copies/Interval
Disk-based Index
RI-tree [26]
growing
space-driven
2
two B+-trees ordered by (bucket,ts ) and (bucket,te )
SP-GiST [18]
fixed
data-driven
1
KD-tree / R-tree
DOT [19]
fixed
space-driven
1
one B+-tree ordered by space-filling curves
IST [21]
growing
data-driven
1
one B+-tree ordered by (te ,ts ) / (ts ,te ) / (d,ts )
SEB [35]
growing
data-driven
1
two-level B+-trees ordered by ts and te
Table 2: Disk-resident interval indexes based on corner structures
30
30
27
27
30
25
25
25
21
21
30
27
27 25
21 18
14
14 12
21
12
18
14
14
12 6
6 2 0
4
8
12
16
20
24
28
0
4
12
9
2 8
12
16
20
24
4
28
0
9
6
4
2
0
(b) query with range [10, 13]
(a) the structure (a) the structure
(b) query with range [10, 13]
6
2
Fig. 10: Corner structure of the segment-tree
Fig. 9: Corner structure of the interval-tree 32
32
when we wish to compute the count of intervals intersecting a range, the number of intervals within each node inside the range can be aggregated directly, without visiting the node. This is particularly beneficial for large ranges that contain multiple nodes, possibly at high levels. First, we focus on the interval-tree. Figure 9a maps the nodes and 13 intervals of Figure 1a into a corner structure, where ts is the x-axis and te the y-axis. Each node corresponds to a rectangular area in the mapped space. For example, node n14 stores intervals intersecting with time 14, i.e., its mapped area is ts ≤ 14 ≤ te . Similarly, n6 is mapped to the space of ts ≤ 6 ≤ te < 14, and n2 corresponds to the space of ts ≤ 2 ≤ te < 6. Figure 9b shows the processing of a range query [10, 13]. Points in nodes (n6 , n14 ) partially intersecting the range must be examined because they may constitute results (for these intervals ts ≤ 13 and te ≥ 10). On the other hand, all intervals in nodes covered by the range (n12 ) are directly reported, because they are query results (for these intervals ts ≥ 10 and te ≤ 13). Similar to the interval-tree, the corner structure for the segment-tree organizes intervals in nodes based on ts and te , without explicitly considering the duration d. Figure 10a maps the nodes of Figure 1b into a 2D space that has a bottom layer of triangle-shaped leaf nodes. Recall that an interval may be partitioned and stored in multiple nodes, possibly at different levels. For instance, s7 = [2, 23) is first assigned to leaf nodes, which are merged recursively, if the parent
4 8
12
8
8
4
16
12
12
8
20
16
16
12
24
20
20
16
28
24
24
20
0
28
28
24
4
32
32
28
12
16
20
24
(a) the structure
28
32
8
4
4
0
4
8
12
16
20
24
28
32
(b) query with range [10, 13]
Fig. 11: Corner structure of HINT
node is fully covered by s7 . The last partition containing te of s7 is stored in leaf node nL23 . The remaining partitions are merged in internal nodes. Specifically, copies of s7 are stored in nodes n4 = [2, 6), n12 = [6, 14), n18 = [14, 21) and nL23 = [21, 23). Internal nodes are mapped to points because they only store intervals covering their full range. A query with range [10, 13] in Figure 10b reports directly the intervals of green-shaded nodes (i.e., n6 , n9 , n12 , nL13 , n13 , n14 ) in the area defined by ts ≥ 10 and te ≤ 13. Intervals in grey nodes (i.e., nR9 ) require inspection. Duplicate elimination is necessary. The corner structure of HINT [10] resembles that of the segment-tree, except that internal buckets correspond to squareshaped areas (instead of points). Both indexes assign intervals to leaf nodes/buckets (represented as triangles) first, and then merge upwards. HINT merges consecutive buck-
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
7
32 28
28
20
20
16
4
8
12
16
20
24
28
32
0
16 12
8 4
8
12
16
20
24
28
32
(b) query with range [10, 13]
Fig. 12: Corner structure of the period-index
ets with the same parent, if they partially intersect an interval (as opposed to fully intersect in the segment-tree). Each internal bucket is represented as a square in Figure 11a), instead of a single point in Figure 10a. The side length of a square is the smallest bucket length (i.e., the bucket length of a leaf node), which is 2 in Figure 11a. For example, bucket b8 (corresponding to range [0, 16)) stores duplicates of intervals with ts ≤ 0 + 2 = 2 and te ≥ 16 − 2 = 14. An interval s7 = [2, 23) incurs only two copies: [2, 16) in b8 and [16, 23) in b20 . Figure 11b shows the processing of a range query [10, 13]. HINT reports directly the intervals of green buckets (i.e., b8 , b10 , bR10 , b12 , b16 ) and requires examination of grey buckets (i.e., bL14 , b14 ). Since the period-index assigns intervals to periods based on their duration, it is better represented by a 2D space, with ts as the x-axis and d as the y-axis. Figure 12a maps the periods of Figure 2 to triangles in a corner structure. Period p0 (p1 ) corresponds to the triangular space with ts , d ∈ [0, 16) (ts , d ∈ [16, 32)). Horizontal lines for duration 8 and 4 subdivide p0 and p1 into three levels L0 , L1 and L2 . Intervals in L0 must have duration d > 8. Accordingly, the valid space of p0 (p1 ) in L0 is restricted to the upper triangle ts ∈ [0, 8) ([16, 24)) and d > 8, shaded in blue. Similarly, intervals in L1 must have duration in the range (4, 8], restricting the valid space of the corresponding buckets to the blue triangles. Intervals falling in a valid space (e.g., s0 , s3 ) are stored directly in the corresponding bucket, whereas the rest (e.g., s2 , s5 , s6 ) generate duplicates in adjacent buckets at the same level. For example, s2 and s5 are duplicated at L1 , while s6 is duplicated at L0 , and stored at both p0 and p1 . Figure 12b shows a query with range [10, 13]. Intervals in the green partition ([8, 16)) are directly reported, while those in grey buckets ([8, 12)) require inspection. It is worth mentioning that the original period-index [4] does not differentiate between the two result types, missing an optimization opportunity. As shown in Figure 13, the RI-tree [26] decomposes the domain (0,32) into equi-length buckets at each level. Therefore, each bucket is mapped to a square-shaped area (instead of a rectangle). The mapping only transforms buckets from the top three levels, because the lowest two levels never re-
8
4 0
(a) the structure
16
12
4
4
20
16
8
8
24
20
12
12
32 28
24
16
16
0
32 28
24
24
4
4
8
12
16
20
24
28
(a) query Bs on (bucket,ts )
32
0
4
8
12
16
20
24
28
32
(b) query Be on (bucket,te )
Fig. 13: Corner structure of the RI-tree
ceive insertions and require no search. A range query of [10, 13] searches the root bucket b16 and then b8 , b12 in a topdown manner. Buckets (e.g., b16 ) that intersect the boundary ts ≤ 13 search B+-tree Bs (Figure 13a), and buckets (e.g., b8 ) that intersect the boundary te ≥ 10 searches Be (Figure 13b). Buckets that are fully covered by the query range (e.g., b12 ) search either Bs or Be . With the exception of the RI-tree, the above indexes lack a maximum (or minimum) capacity constraint. Thus, their nodes or buckets may be very unbalanced. This is particularly true for the interval-tree, where top level nodes (e.g., n14 in Figure 9) may include most intervals. In addition, each node may contain intervals with large duration variance. The other structures alleviate these problems at the expense of redundancy. In addition to its negative effect on index size, redundancy necessitates duplicate elimination, increasing the cost and complexity of query processing. Interval- and segment-trees aim at static intervals, which must be known in advance. HINT supports insertions of new intervals, but the domain and the number of partition levels are predefined and fixed. Methods based on spatial indexes (e.g., [18, 19]) also assume a fixed temporal domain. One-level interval indexes (e.g., IST [21], the RI-tree [26]) can handle ever increasing time, but insertions may occur in arbitrary data nodes, i.e., all nodes are mutable. Numerous mutable nodes have negative effects on performance because they are: (i) under-utilized in terms of capacity (increasing the total index size), (ii) accessed during queries because they are open-ended. If intervals arrive in increasing ending time (IET), the only way to maximize immutable nodes and achieve appendonly insertions is through a two-level structure, such as SEB [35], with increasing te at the bottom layer. However, SEB suffers from a serious problem: the last node of every bottom tree (e.g., D5 , D4 in Figure 8a) is mutable since it could receive an interval with very low ts and long duration. As shown in our experimental evaluation, for real datasets there are thousands or millions of such nodes. In the following, we utilize our observations, to develop improved indexes for temporal intervals.
8
Kai Wang et al.
4.1 Insertions
19
12
0
4
8
12
16
20
24
28
0
(a) nodes
(b) the structure
Fig. 14: CEB
4 CEB
We first propose CEB (Center and Endpoint B-tree), which aims at improving SEB by decreasing the mutable nodes. CEB consists of two layers of append-only B+-trees. The e top tree is ordered by the center point (c = ts +t 2 ) of intervals. The leaf nodes of the top tree correspond to the root nodes of bottom trees (BTs), which are B+-trees ordered by te . Finally, the leaves of BTs are data nodes that store the records (interval + payload). Each leaf node of the top and bottom trees stores a pointer to its next sibling. Under the IET assumption, a new interval is inserted into the latest leaf node of the BT that corresponds to its center point. A BT is min , keymax ] (range of center points). The adbounded by (keytop top max < now vantage compared to SEB is that the BTs with keytop 2 will never receive insertions and are compressed to full, immutable nodes, whereas, in SEB the last node of every BT is mutable. Figure 14a shows an example CEB assuming that the data node capacity is 3. The root node of the top tree has four leaf nodes pointing to bottom tree roots BR0 , BR1 , BR2 , BR3 separated by center point keys 6, 16.5 and 23.5. Specifically, all intervals with c ≤ 6 fall under BR0 , with c ∈ (6, 16.5] fall under BR1 etc. BR1 separates its data nodes by endpoint te = 19. A new interval (with te ≥ 30) may only be inserted into D3 , D2 , or BR3 . D0 can never receive insertions because the current time 30 > 2 · 6 (twice its maximum center point). Figure 14b shows the corner structure, where the x-axis is c, and the y-axis is te . All intervals appear above the diagonal line because te > c. Four bottom trees BT0 , BT1 , BT2 and BT3 correspond to four adjacent columns on the x-axis, separately by 6, 16.5 and 23.5. Their respective data nodes are rectangular partitions on the te -axis. Each interval maps to a point into a data node based on its c and te . For instance, intervals with c ∈ (6, 16.5] are mapped to points in D1 or D3 (of BT1 ), with D1 storing older, and D3 more recent intervals. The gray data space above D0 will never receive insertions.
We adopt the AP-tree [33] to facilitate append-only insertions for top tree and bottom trees. Each root (T R or BR) stores a pointer to its last leaf node, where insertions may occur. Algorithm 1 describes insertion of interval I and its payload P. First, CEB searches the top tree T T for the bottom tree root BR containing the center keytop of I (line 5). Then BR returns the last data node DN of its bottom tree BT . If DN is not full, CEB appends I and P into DN (line 8) and the insertion terminates. Otherwise, DN requires overflow processing, generating a new data node (lines 12-24). There are three cases of splits: – Case 1: horizontal split only, in lines 13-16. – Case 2: vertical split only, in lines 17-21. – Case 3: vertical and horizontal split, in lines 17-24. If the overflowed node DN is not a bottom tree root BR, new , CEB splits horizontally at the largest ending time keyte new generating data node DN for the insertion (Case 1). If the overflowed node DN is a bottom tree root BR (i.e., BT has a single data node DN), CEB splits vertically at the maximum new , creating BT new with root BRnew (lines center point keytop new 19-20). BR is also a data node, storing intervals with cennew . Given that only the latest BT root ter points in c ≥ keytop can be a data node, BR is upgraded from a leaf to a branch new , node (lines 17-18), which has a single child. If I.c > keytop new the insertion falls into BR of BTnew (Case 2). Otherwise (Case 3), CEB requires another horizontal split at the curnew , creating data node DN rent largest ending time keyte new in BT (lines 22-24) for insertion. Figure 15 illustrates the insertion of the ten intervals s0 , ..., s9 of Figure 14 into CEB (assuming data node capacity 3). Initially (Figure 15a), the top tree root T R has a single child BR0 , which is both a BT root and a data node D0 , containing s0 , s1 and s2 . In Figure 15b, the next insertion s3 forces D0 to overflow at current maximum center point 6 (i.e., center of s2 ), generating BT1 with a single data node D1 , which is also a root BR1 (Case 2). Interval s3 is inserted into D1 because its center point c > 6. BR0 is upgraded from leaf to branch node, pointing to D0 . BT0 with center range c ∈ (0, 6] becomes immutable because now = 13 ≥ 6 · 2, i.e., BT0 never receives new points. In Figure 15c, s4 and s5 both have center point above 6 and should be inserted into the latest data node under BR1 . Inserting s6 causes D1 to overflow at its current largest c = 16.5, generating BT2 with a single data node D2 . Meanwhile, BR1 is upgraded to a branch node, pointing to immutable D1 . Since s6 has c ≤ 16.5 and should be inserted into BT1 , D1 overflows at its current largest te = 19 (Case 3), generating a new data node D3 to accommodate s6 . In Figure 15d, new insertions either fall into D3 (e.g., s7 ) or D2 (e.g., s8 and s9 ) according to their center points. The following Lemma 1 analyzes the insertion cost of CEB.
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
0
(a) 3-rd insertion
9
19
19
12
12
12
0
0
0
(b) 4-th insertion
(c) 7-th insertion
(d) 10-th insertion
Fig. 15: Insertions of CEB Algorithm 1 Inserting a new record (I: Interval, P: Payload) 1: procedure INSERT RECORD(I, P) 2: if T T is empty then 3: Initialize the top tree T T 4: keytop ← (I.ts + I.te )/2 ▷ Compute the top key (center) 5: BR ← find the bottom root corresponding to keytop in T T 6: DN ← latest data node in the bottom tree of BR 7: if DN is not full then 8: Insert (I, P) to DN 9: else ▷ DN is full 10: DN new ← PROCESS OVERFLOW(BR, DN, keytop ) 11: Insert (I, P) to DN new 12: procedure PROCESS OVERFLOW(BR, DN, keytop ) 13: if DN ̸= BR then ▷ Case 1 new ← ending time of the last interval in BR 14: keyte new 15: DN new ← add new data node to BR’s tree with keyte 16: return DN new ▷ If DN is also the bottom tree root 17: DN ′ ← transfer the data in DN to another page 18: Upgrade BR to a branch node pointing to DN ′ new ← maximum top key in DN 19: keytop new 20: BRnew ← add new leaf node to T T with keytop new < key new 21: if keytop then return BR ▷ Case 2 top 22: 23: 24:
new ← ending time of the last interval in BR keyte new DN new ← add new data node to BR’s tree with keyte return DN new
▷ Case 3
Lemma 1 When there are N intervals in m bottom trees, a CEB insertion has I/O cost O(logB m + B1 · logB N + Nm · logB m), where B is the capacity of a disk page. Proof Each insertion always incurs cost CSearch to find the proper leaf node. Locating the bottom tree, is bounded by the depth of the top tree O(logB m). Since each bottom tree is append-only, fetching its last node costs only O(1). Therefore, the cost of insertions in the absence of overflows is
dominated by the search cost CSearch = O(logB m). In addition, overflows require a horizontal split (Case 1) with cost CHS , or vertical split (Case 2) with cost CV S or both (Case 3) with cost CHS + CV S . A horizontal split inserts a new data node into a bottom tree5 , and may propagate all the way up to its root with cost bounded by the depth of the largest bottom tree O(logB N). In the worst case (Case 1&3), a horizontal split occurs after every O(B) insertions; thus, the amortized CHS = O( B1 · logB N). Moreover, an insertion may incur a vertical split with a probability Nm , generating a single-node bottom tree, which requires an insertion into the top tree with O(logB m) cost. Therefore, the amortized cost CV S = O( Nm · logB m). Adding the three terms together: CSearch +CHS +CV S = O(logB m + B1 · logB N + Nm · logB m). As an additional step to reduce the number of bottom trees, CEB conducts a periodic check that identifies branches of the top tree having only immutable BTs, and compacts them into a single balanced B+-Tree containing all points (of the immutable BTs). Since the data nodes of individual BTs are already ordered on te , we merge them to form a single sorted linked list of dead data nodes. We then iterate through this list packing every CB data nodes in a new branch, where CB is the branch capacity. We repeat recursively to create higher level branches in a bottom-up routine. This local bulk loading process replaces CB immutable BTs (whose last data node can be almost empty), with a single B+-tree where all nodes, except possibly for the last one, are full. The compaction step is not applicable to SEB because all its BTs are mutable. 5
A horizontal split has no cost for the top tree.
10
Kai Wang et al.
Algorithm 2 Searching a range ([qs , qe ]) in CEB
0
Fig. 16: Range query [qs , qe ] in CEB
1: procedure RANGE QUERY([qs , qe ]) 2: R ← {} ▷ Result Intervals 3: BT ← find the bottom tree containing center point q2s min ← minimum top key in BT 4: keytop min ≤ qe +now do 5: while keytop 2 max 6: keytop ← maximum top key in BT min − q ) in BT 7: DN ← find the data node for max(qs , 2 · keytop e 8: while DN ̸= null do min ← first key of DN 9: keyte max ← last key of DN 10: keyte min < max(q , 2 · keymax − q ) then 11: if keyte s e top 12: Append qualifying records of DN to R 13: else 14: Append all records of DN to R ▷ Report 15: DN ← next DN min ← keymax 16: keytop top 17: BT ← next BT 18: return R
4.2 Range Queries Given a range query q = [qs , qe ], CEB returns intervals fulfilling constraints ts = 2c − te ≤ qe (slash boundary) and te ≥ qs (horizontal boundary). Notably, the query searches bottom trees with center points in [ q2s , qe +now ], which cor2 responds to the green area in Figure 16. Observe that center points within the triangular region bounded by qe and qe +now may correspond to qualifying intervals with ts ≤ qe . 2 On the other hand, bottom trees with (i) maximum center max before qs contain (unqualified) intervals that point keytop 2 min after end before qs , and (ii) minimum center point keytop qe +now have intervals that start after qe . In Figure 16, BT0 2 and BT1 are excluded by case (i), while BT6 by case (ii). In the rest of the bottom trees (BT2 to BT5 ) intervals in nodes included by the range (e.g., D7 , D8 , D10 , D11 ) are directly reported, while those in nodes partially overlapped (e.g., D4 , D5 , D6 , D9 ) are evaluated. Algorithm 2 shows the pseudocode for range query processing [qs , qe ]. CEB accesses bottom trees with center points ranging from q2s (line 3) to qe +now (line 5). Searching a BT 2 starts from the data node containing qs (horizontal boundmin −q (slash boundary) (line 7), until reaching ary) or 2·keytop e the last data node (line 8). Intervals of the first node must be individually examined (lines 11-12), while those of the remaining nodes are directly reported (lines 13-14). Lemma 2 When there are N intervals in m bottom trees, a stabbing/range query of CEB has I/O cost O(logB m + m logB N + Bk ), where k is the number of query results. Proof Given a range query [qs , qe ], CEB locates the first bottom tree with cost O(logB m). In each BT, finding the first intersected data node has cost O(logB N). The total number of data nodes containing k results is Bk , and all these nodes are retrieved. Combining the terms, we obtain the total cost as O(logB m + m logB N + Bk ).
CEB can easily be extended to count queries, returning only the number of intersected intervals, as opposed to their IDs. In this case, intervals in immutable nodes fully covered by the range (i.e., D7 , D10 , D11 of Figure 16) are directly aggregated to the total count, without requiring disk accesses. Since such nodes are fully packed, their number of intervals is fixed. Disk accesses are only necessary for partially overlapped (e.g., D4 , D5 , D6 ) or mutable nodes (e.g., D8 , D13 ). 5 TIDE TIDE (time intervals by duration and endpoint) aims at minimizing the number of bottom trees, by ordering the top tree on duration d, and BTs on ending time te . Duration is a property that does not necessarily increase as time evolves. This is particularly true for regular datasets, such as transportation (e.g., taxi trips, flights) intervals, where d is independent of the length of the recorded history. For instance, the average flight time (e.g., a few hours) does not increase based on the years of stored flights. As another example, intervals produced by IOT devices or wireless sensors have a fixed length determined by the sampling or transmission frequency. Especially for regular datasets, TIDE leads to a very small number of bottom trees (several orders of magnitude below SEB and CEB), facilitating high compactness and cache locality (i.e., most non-full nodes are cached). Figure 17a shows an example of TIDE storing thirteen intervals (same examples in Figure 14). The root node of the top tree T R contains three leaf nodes, corresponding to three bottom tree roots BR0 , BR1 and BR2 , separated by duration keys 6 and 21. BR0 (BR1 ) separates its data nodes with ending time keys 9 and 25 (23). BR2 is both a root and a data node. A new interval (with te ≥ 30) may only be inserted at D5 , D4 or BR2 . Figure 17b shows the corresponding corner structure in the duration and end-time 2D space. All inter-
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
data node D1 , which is also a BT root BR1 (Case 2 in Section 4.1). Interval s3 is inserted into D1 , since it has duration d > 6. BR0 is upgraded from leaf to branch node, pointing to D0 . In Figure 18c, s4 has duration below 6 and should be inserted into the latest data node under BR0 , forcing D0 to overflow at its maximum te = 9 (Case 1). A new data node D2 accommodates s4 , and D0 becomes immutable. Future insertions either fall into D1 (e.g., s6 and s7 ) or D2 (e.g., s5 and s8 ) according to their duration. In Figure 18d, inserting s9 causes D1 to overflow at its current largest d = 21, generating BT2 with a single data node D3 . Meanwhile, BR1 is upgraded to a branch node, pointing to immutable D1 . Since s9 has d ≤ 21 and should be inserted into BT1 , D1 overflows at its current largest te = 23 (Case 3), generating data node D4 to insert s9 . Theoretically, TIDE has the same insertion cost as CEB (CSearch + CHS + CV S in Lemma 1). In practice, CSearch and CV S of TIDE are negligible since m << N, and CHS dominates the insertion cost of TIDE. The compaction step of CEB for immutable bottom trees is not applicable to TIDE because all BTs may receive insertions, given that future intervals may have any duration.
25 23
9
0
4
8
12
16
20
24
0
28
(a) nodes
11
(b) corner structure
Fig. 17: TIDE
vals appear on the upper half of the diagonal te = d. The three bottom trees correspond to three adjacent columns on the d-axis, separated by 6 and 21. Each interval maps to a point into a data node based on its d and te . For instance, intervals with d ∈ (6, 21] are mapped to points in D1 or D4 (of BT1 ), with D1 storing older, and D4 more recent intervals.
5.1 Insertions Insertions of TIDE are similar to CEB, except for computing the top key. Specifically, line 4 in Algorithm 1 is replaced with keytop ← I.te − I.ts . The rest of the process is unchanged. Figure 18 illustrates the insertion of the ten intervals s0 , ..., s9 of Figure 17 into TIDE (assuming data node capacity 3). Initially (Figure 18a), the top tree root T R has a single child BR0 , which is both a bottom tree root and a data node D0 , containing s0 , s1 and s2 . In Figure 18b, the next insertion s3 forces D0 to overflow at current maximum duration 6 (i.e., duration of s2 ), generating BT1 with a single
5.2 Range Queries Since the top tree organizes intervals by duration, it is not useful for range queries. Instead, given a range query [qs , qe ], where qs ≤ qe , TIDE searches all bottom trees and returns intervals fulfilling te ≥ qs (horizontal boundary) and ts ≤ qe (diagonal boundary). Figure 19 shows an example range, where the result area is shaded in green. For instance, nodes in BT0 with possible results (i.e., D2 , D5 and D6 ) intersect
23
0
0
(a) 3-rd insertion
(b) 4-th insertion
9
9
0
0
(c) 5-th insertion
Fig. 18: Insertions in TIDE
(d) 10-th insertion
12
Kai Wang et al.
Lemma 3 When there are N intervals in m bottom trees, a stabbing/range query of TIDE has I/O cost O(m logB N + Bk ), where k is the number of query results. Proof Given a range query [qs , qe ], TIDE searches (in each bottom tree BTi ) for the data node containing qs with cost O(logB N). Then it scans its siblings until finding the data node containing qe + keymax (i.e., the maximum duration in d a bottom tree) or the last data node. The total number of data nodes containing k results is Bk . Combining the search and scan terms, we obtain O(m logB N + Bk ). 0
Fig. 19: Range query [qs , qe ] in TIDE [qs , qe + d1 ]. Nodes below the horizontal boundary te < qs contain intervals that end before qs , whereas nodes above the diagonal boundary ts > qe have intervals that start after qe . Similarly, in BT1 nodes possibly containing results are D1 , D7 and D9 . Intervals in nodes, such as D4 , covered by the range are directly reported. Algorithm 3 shows the pseudocode for range query processing [qs , qe ]. Each bottom tree BT stores intervals with min to keymax , shaped as a column. durations ranging from keytop top Searching a bottom tree starts from the data node containing qs (line 7), and stops when reaching the data node containmax (lines 11-12) or the last data node (line 8). ing qe + keytop Under the unified representation, TIDE identifies nodes that can be directly reported (i.e., all its intervals are results), if min and keymax ≤ q +keymin (lines 13-14). The interqs ≤ keyte e te top vals of the remaining searched nodes may constitute results, and must be individually examined (lines 15-16). Algorithm 3 Searching a range ([qs , qe ]) in TIDE 1: procedure RANGE QUERY([qs , qe ]) 2: R ← {} ▷ Result Intervals 3: BT ← earliest bottom tree min ← 0 4: keytop 5: while BT ̸= null do max ← maximum top key in BT 6: keytop 7: DN ← find the data node for qs in BT 8: while DN ̸= null do min ← first key of DN 9: keyte max ← last key of DN 10: keyte max < keymin then 11: if qe + keytop te 12: break min max ≤ q + keymin then 13: if qs ≤ keyte and keyte e top 14: Append all records of DN to R ▷ Report 15: else 16: Append qualifying records of DN to R 17: DN ← next DN min ← keymax 18: keytop top 19: BT ← next BT 20: return R
Similar to CEB, count queries (returning only the number of intersected intervals) require no disk accesses for immutable nodes fully covered by the range (e.g., D3 , D4 of Figure 19). TIDE can also efficiently process queries with length constraints, e.g., find all intervals in [qs , qe ] with duration in the range [ds , de ]. 6 In this case, the top tree is used to identify bottom trees with intervals satisfying [ds , de ]. Even for conventional ranges (without duration constraints), where all m bottom trees are accessed, TIDE’s query performance is outstanding because m is very low in real-world datasets. We experimentally evaluate our claims in the next section. 6 Experimental Evaluation The evaluation was conducted on Ubuntu Linux with an AMD Ryzen Threadripper 3960X 3.8GH CPU and 64GiB RAM. We developed a generic disk-based framework for historical indexes in Rust, implemented TIDE, CEB and SEB using the same append-only B+-tree structures [33], and compared them with the state-of-the-art RI-tree: – TIDE: two-level B+-trees ordered by d and te e – CEB: two-level B+-trees ordered by c = ts +t 2 and te – SEB [35]: two-level B+-trees ordered by ts and te – RIT [26]: a B+-tree Bs ordered by (bucket,ts ) and another Be ordered by (bucket,te ). The disk-page and LRU cache sizes are set to 4KiB and 4MiB, respectively, for all experiments (different cache sizes exhibit similar performance). We use the following real datasets, summarized in Table 3: – TAXI 7 : 3 billion taxi trips with pick up and drop off timestamps (in seconds), during 2011-2025. – BIKE 8 : Start and end timestamps (in seconds) of 100M bicycle trips, during 2014-2020 in New York City. – NFT 9 [12]: 28M intervals denoting the stable price period (in seconds) of non-fungible tokens from OpenSea transactions, during 2021-2023. 6 The RI-tree cannot answer such queries because t and t of each s e interval are stored separately (i.e., interval durations are lost). 7 https://www.nyc.gov/site/tlc/index.page 8 https://citibikenyc.com/system-data 9 https://huggingface.co/datasets/MLNTeam-Unical/ NFT-70M_transactions
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
13
TAXI
BIKE
NFT
AMAZON
Object Interval #Intervals
NYC taxi driving trips 3198336346 (3.2 billion)
NYC bicycle riding trips 100507903 (100.5 million)
non-fungible token unchanged price 28581957 (28.6 million)
online item unchanged rating 439293331 (439.3 million)
Min. Duration
1 second
60 seconds
1 second
1 second
Avg. Duration
1115 secs (0.0002%) (18.6 minutes)
984 secs (0.0004%) (16.4 minutes)
2724947 secs (3.2%) (1 month)
2789003 secs (1.0%) (1 month)
Max. Duration
76709271 secs (16.2%) (2.4 years)
19513649 secs (8.8%) (7.4 months)
83743716 secs (99.6%) (2.7 years)
288272408 secs (99.2%) (9.1 years)
Table 3: Properties of interval datasets TAXI
BIKE
end time (te)
2e5
6e6
2e5
5e6
1e5
3e6
6e4
2e6 0e
6e4 1e5 2e5 2e5 3e5
AMAZON
2.0e7
8e6
3e5
0e
NFT 1.6e6
1.5e7
1.2e6
1.0e7
8.0e5
5.0e6
4.0e5
2e6 3e6 5e6 6e6 8e6
start time (ts)
5.0e6 1.0e7 1.5e7 2.0e7
start time (ts)
4.0e5 8.0e5 1.2e6 1.6e6
start time (ts)
start time (ts)
Fig. 20: 10k data points sampled from datasets Dataset
TAXI
BIKE
NFT
AMAZON
TIDE
SEB
CEB
RIT
TIDE
SEB
CEB
RIT
TIDE
SEB
CEB
RIT
TIDE
SEB
CEB
RIT
Size (GiB)
44.95
51.00
49.65
153.92
1.22
2.06
1.87
4.34
0.91
1.03
1.02
3.12
7.40
7.80
7.68
25.49
#Bottom Trees
7
1072630
830253
-
4
145523 112245
-
34
20449
18870
-
243
72852
50327
-
#Data Nodes 11758592 12293769 12171730 40093046 320091 395187 378364 1129963 238201 248306 247560 813520 1935334 1971373 1960372 6643454 #All Nodes
11784554 13368766 13015317 40347903 320801 541031 491184 1137159 238748 268800 266626 818098 1939736 2044385 2012627 6680749
Table 4: Index size and number of nodes – AMAZON 10 [22]: 439M intervals corresponding to the rating period (in seconds) of Amazon items, during 20142023. Figure 20 plots a sample of 10k data points from the four datasets. TAXI and BIKE are regular, i.e., interval durations are short and independent of the length of recorded history. Accordingly all data points lie close to the ts = te diagonal line. On the other hand, NFT and AMAZON have high variance. As shown in Table 3, the average and maximum duration for TAXI (BIKE) is only 0.0002% (0.0004%) and 16.2% (8.8%) of the whole extent of the dataset, in comparison to NFT’s 3.2% and 99.6% (AMAZON’s 1.0% and 99.2%). Section 6.1 investigates the size and other index characteristics, while Sections 6.2 and 6.3 evaluate insertion and query performance, respectively. 10
https://amazon-reviews-2023.github.io/
6.1 Index Characteristics We built indexes by sequentially inserting the records of TAXI, BIKE, NFT and AMAZON datasets. Table 4 lists various properties of the structures generated by TIDE, SEB, CEB and the RI-tree. Indexes with two-level append only B+-trees (i.e., TIDE, SEB, CEB) are significantly more compact than the RI-tree, which consumes more than three times the size of TIDE. This is because the RI-tree (i) inserts each interval into two B+-trees Bs and Be , generating two copies, and (ii) all its data nodes are mutable, and possibly underutilized. For the regular datasets TAXI and BIKE, TIDE creates only seven and four bottom trees, respectively. For the irregular, NFT and AMAZON, the number of BTs increases to 34 and 243, which however is significantly below that of SEB and CEB, which may reach up to millions. The compaction step of CEB reduces the number of BTs 8% − 30%,
Kai Wang et al. AMAZON
2
3
4
5
6
7
1
2
3
4
0
5
10 15 20 25 30 35
0
40
80 120 160 200 240 Index = SEB
# Data Nodes # Data Nodes
34M 1M 33k 1k 32 1
NFT
total no. of data nodes
1 34M 1M 33k 1k 32 1
BIKE
Index = TIDE
TAXI
34M 1M 33k 1k 32 1
total no. of data nodes
0
200k 400k 600k 800k 1M
0
35k
70k
105k
140k
4k
8k
12k
16k
20k
12k 24k 36k 48k 60k 72k Index = CEB
# Data Nodes
14
total no. of data nodes
0
200k
400k
600k
Bottom Tree
800k
0
20k 40k 60k 80k 100k
3k
Bottom Tree
6k
9k 12k 15k 18k
10k
Bottom Tree
20k
30k
40k
50k
Bottom Tree
Fig. 21: Number of data nodes per bottom tree
Figure 21 contains twelve plots, each measuring the number of data nodes (y-axis) stored in the corresponding bottom tree (x-axis) for TIDE (first row), SEB (second row) and CEB (third row). Each column corresponds to a dataset. The horizontal line in each diagram denotes the total number of data nodes. For TAXI (BIKE), the first three (one) BTs of TIDE contain the shortest 96% (98%) intervals, and the remaining trees contain fewer data nodes with increasing interval durations. On the other hand, SEB and CEB have thousands or millions BTs, each with up to 30 data nodes. Data nodes of SEB and CEB have a similar extent in te , which is significantly higher than the average node extent in TIDE. Long nodes negatively affect performance as they are expected to intersect more queries. For the irregular datasets, the first two bottom trees of TIDE contain the majority (56%) of data nodes in NFT, whereas the first two BTs only occupy 16% data nodes in AMAZON. In case of SEB and CEB, since the latest intervals in NFT and AMAZON are less likely to have started as recently as in the regular datasets, they are more prone to fall into older BTs.
TIDE
1G
I/O Cost
depending on the dataset, compared to SEB. The index size is dominated by the data nodes in most cases. The only exception is SEB and CEB for BIKE, where SEB (CEB) data nodes only amount to 73% (77%) of the total, and the bottom tree roots make up nearly a quarter of all the nodes. Furthermore, each root of the mutable BTs contains only a handful of data node entries, the last of which is only partially filled. Consequently, for BIKE, SEB (CEB) consumes 1.7x (1.5x) more space than TIDE, which is fully packed, except for the last data node of its four bottom trees.
SEB
CEB
RIT 204.9 187.8 139.1
100M 1.3
2.3
3.4
113.0 91.7
67.4
10M 1M 100k
1.8
TAXI
3.0
BIKE
3.6
NFT
AMAZON
Fig. 22: I/O cost of inserting the full dataset
This leads to fewer BTs on irregular, compared to regular datasets.
6.2 Insertion Performance Figure 22 shows the I/O cost (total number of page read and write operations) after inserting all records of TAXI, BIKE, NFT and AMAZON, using a 4MiB LRU buffer. TIDE, SEB and CEB follow similar append-only frameworks, caching the last (mutable) data node of their most recent BTs, whereas the RI-tree caches disk pages of recent buckets. The number above each bar indicates how many times each method is more costly than TIDE. For regular datasets, TIDE is a few times faster than the rest, while for the irregular ones, it is hundreds of times faster. Given the low number of bottom trees (see Figure 21), TIDE keeps in the LRU buffer the last (mutable) data node of every BT, and the entire top tree. This is not possible for SEB and CEB because of their numerous BTs. Thus, search-
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
ing for the proper data node to accommodate an insertion incurs I/O cost. Moreover, SEB and CEB suffer from numerous vertical splits (on a large top tree). For the RI-tree, insertions in TAXI and BIKE often fall into recent buckets (e.g., b28 in Figure 13), which are cached. However, it still incurs three times more I/O cost than TIDE due to its larger index size. For the irregular datasets (NFT and AMAZON), high duration variance impacts cache locality in SEB (CEB) based on ts (c), i.e., the insertion of long intervals necessitates fetching from the disk nodes with low ts (c), which have not been accessed recently. CEB saves I/O cost over SEB because its insertions must fall into mutable BTs (i.e., c ≥ now 2 ), enabling better cache locality. In comparison to SEB, the RI-tree demonstrates better cache locality on irregular datasets because its insertions fall into very few buckets (e.g., b16 , b24 and b28 in Figure 13).
20% to 90% cheaper, independently of the dataset characteristics.
6.3 Query Performance Figure 23 shows the I/O cost of stabbing queries and ranges covering 0.0001% to 0.1% of the total history. Each reported result is the average of 1000 uniformly distributed queries. The mean output cardinality is above the diagrams. The number on top of each bar shows the ratio of the query cost over TIDE. TIDE is up to several orders of magnitude faster than SEB and CEB on regular datasets, and a few times faster on irregular ones. CEB is better than SEB in datasets (TAXI, BIKE, AMAZON) that achieves high compression (22% 30%). The exception is NFT, where the compression is only 8%. Naturally, the relative performance difference of SEB and CEB (wrt to TIDE) decreases with the output cardinality 11 since all methods have to access the data nodes with qualifying intervals. Compared to the RI-tree, TIDE is between 11 Observe that even a stabbing query retrieves 1 million (5 million) intervals in NFT (AMAZON), and this number remains almost the same for all ranges. This is due to the long average interval duration in irregular datasets (see Table 3).
TAXI # Records 11k
I/O Cost
1M
15k 11k 13k 10k 5k 4k
855 641 92 69
100k
1.9
10k
1.9
1k
NFT
100
394
10
100k
1k
CEB
0.1
AMAZON
RIT
# Records
10k
95k
1M
1M
1M
# Records
1M
1M
100k 7k 7k
7k 6k
6k 5k
2k 2k
356315 2.3
10k
10 stab 0.0001 0.001 0.01
488
1M
100
1.3
% Range
SEB
3.2
2.3
1.5
1k
1.7 1.2
Figure 24 shows the I/O cost of count queries for ranges covering 0.001% to 10% of history. A count query only returns the number of qualifying records, shown on top of each plot, instead of retrieving their IDs. Compared to conventional ranges, they incur less I/O cost in TIDE, CEB and SEB because they aggregate directly the results of full nodes covered by the query. Only partially intersecting and mutable nodes need to be visited. The benefits of TIDE are even more substantial in this setting, outperforming CEB and SEB 3-5 (1-2) orders of magnitude in regular (irregular) datasets. This is because CEB and SEB examine numerous irrelevant mutable nodes, which cannot be covered since they are open-ended. The RI-tree must access all data nodes because they are all mutable. Consequently, its cost is the same as that of conventional range queries, and its relative performance to TIDE is much worse than Figure 23.
# Records
43k 328k 3M
10M
The main reason for the superiority of TIDE is a low number of BTs, whose high level nodes reside in the LRU buffer, reducing disk accesses. In contrast, SEB searches numerous BTs with ts ≤ qs because any interval starting before qs may die after qe . For instance, a stabbing query in the middle of the data space is expected to visit at least half of the 1072630 BTs on TAXI, which cannot be cached, leading to frequent disk accesses. Moreover, SEB has another serious weakness: BTs with small ts rarely contain results, although their mutable nodes intersect qs . Such nodes can be very long (they extend to the current time), but are not likely to receive insertions because most regular intervals are short. CEB has a similar weakness: BTs with large centers (c ∈ [qe , qe +now ]) rarely contain results, but require ac2 cesses. The absolute cost of SEB and CEB remains rather stable with the output cardinality, indicating that it is dominated by visits to irrelevant nodes. Despite a large index size, the RI-tree has competitive query performance because very few (≤ 2·h) accessed data nodes contain irrelevant intervals.
BIKE TIDE
8k
15
1.9
3.2
2.3
1.5
3.2
2.3
1.5
3.2
2.3
3.2
100k
5M
5M
5M
5M
5M
4.2 3.7
4.2 3.7
4.2 3.7
4.2 3.7
3.9 3.5
1.6
1.6
1.6
1.7
1.6
1.5
1.5
10k
10k
1.7 1.2
1.2
1.3
1k
stab 0.0001 0.001 0.01
0.1
1k stab 0.0001 0.001 0.01
% Range
Fig. 23: Range queries
% Range
0.1
stab 0.0001 0.001 0.01
% Range
0.1
16
Kai Wang et al. TAXI
BIKE
NFT TIDE
Count 43k 328k 3M
10M I/O Cost
1M
861 476 395 722
42
1k
1k
10k
1M 100k
6
100
10
7k 6k
7k 6k
7k 6k
5k 5k
0.1
1
% Range
10
1M
1M
Count 1M
4M 36
4k 4k 2k
8
10
8
10
9
10
5M
5M
9M
51M
53 52
53 54 49 50 51
1M
11
12
100k
10k
35
5M
234
21
18
17
17
17 10
271
53 52
53 52 23
26
23
10k
5 2
10 0.001 0.01
1M
100k
1k
100
AMAZON
RIT
Count
95k 945k 10M
10k
276
10k
CEB
Count
32M 325M
19k 15k 19k 14k 13k 10k 3k 3k
100k
SEB
1k 0.001 0.01
0.1
1
10
1k 0.001 0.01
% Range
0.1
1
% Range
10
0.001 0.01
0.1
1
10
% Range
Fig. 24: Count queries 7 Conclusion Under the IET assumption, intervals are inserted in increasing order of their ending time te . SEB, the only existing index aimed at IET, follows a 2-level architecture where a top tree orders intervals on starting time ts , while the bottom trees organize intervals on te . We first propose CEB, as an optimization of SEB, which reduces the index size. The top tree of CEB organizes intervals by their center point c; accordingly, bottom trees with c < now 2 are immutable and compressed. Nevertheless, CEB suffers from similar drawbacks as SEB, namely, due to the ever increasing value of c and ts , the number of BTs is unbounded. To avoid this problem, our second contribution TIDE organizes intervals at the top tree based on their duration d. This leads to a very small number of bottom trees, compact index size, good cache locality and improved update/query performance. The IET assumption facilitates fast insertions through append-only B+trees. In addition, it enables immutable nodes that can be full, minimizing the total index size. Subsequently, all indexes aimed at IET have smaller size and faster insertions than other disk-resident interval indexes. For instance, SEB, CEB and TIDE are about three times smaller than the state-of-the-art RI-tree for all the evaluated datasets and faster for insertions of regular datasets. Moreover, TIDE is always the most efficient on query processing under all settings. Compared to the RI-tree, whose 2-tree structure is highly optimized for range queries, TIDE is also more flexible and can effectively process a variety of other tasks, including count and duration queries. Acknowledgements This work was supported by GRF grant 16208623 from Hong Kong RGC.
References 1. Amagata, D.: Independent range sampling on interval data. In: 2024 IEEE 40th International Conference on Data Engineering
(ICDE), pp. 449–461 (2024). DOI 10.1109/ICDE60146.2024. 00041 2. Arge, L., Vitter, J.: Optimal dynamic interval management in external memory. In: Proceedings of 37th Conference on Foundations of Computer Science, pp. 560–569. IEEE Comput. Soc. Press (1996). DOI 10.1109/SFCS.1996.548515 3. Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The r*tree: an efficient and robust access method for points and rectangles. SIGMOD Rec. 19(2), 322–331 (1990). DOI 10.1145/93605. 98741. URL https://doi.org/10.1145/93605.98741 4. Behrend, A., Dignös, A., Gamper, J., Schmiegelt, P., Voigt, H., Rottmann, M., Kahl, K.: Period index: A learned 2d hash index for range and duration queries. In: Proceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD ’19, p. 100–109. Association for Computing Machinery, New York, NY, USA (2019). DOI 10.1145/3340964.3340965. URL https://doi.org/10.1145/3340964.3340965 5. Berg, M.d., Cheong, O., Kreveld, M.v., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd ed. edn. Springer-Verlag TELOS, Santa Clara, CA, USA (2008) 6. Bouros, P., Christodoulou, G., Rauch, C., Titkov, A., Mamoulis, N.: Querying interval data on steroids. IEEE Transactions on Knowledge and Data Engineering (2025) 7. Bouros, P., Mamoulis, N., Tsitsigkos, D., Terrovitis, M.: Inmemory interval joins. The VLDB Journal 30(4), 667–691 (2021). DOI 10.1007/s00778-020-00639-0. URL https://doi.org/ 10.1007/s00778-020-00639-0 8. Brodal, G.S., Rysgaard, C.M., Svenning, R.: External memory fully persistent search trees. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, p. 1410–1423. Association for Computing Machinery, New York, NY, USA (2023). DOI 10.1145/3564246.3585140. URL https: //doi.org/10.1145/3564246.3585140 9. Ceccarello, M., Dignös, A., Gamper, J., Khnaisser, C.: Indexing temporal relations for range-duration queries. In: Proceedings of the 35th International Conference on Scientific and Statistical Database Management, SSDBM ’23. Association for Computing Machinery, New York, NY, USA (2023). DOI 10.1145/3603719.3603732. URL https://doi.org/10.1145/ 3603719.3603732 10. Christodoulou, G., Bouros, P., Mamoulis, N.: Hint: A hierarchical index for intervals in main memory. In: Proceedings of the 2022 International Conference on Management of Data, SIGMOD ’22, p. 1257–1270. Association for Computing Machinery, New York, NY, USA (2022). DOI 10.1145/3514221.3517873. URL https: //doi.org/10.1145/3514221.3517873 11. Christodoulou, G., Bouros, P., Mamoulis, N.: Lit: Lightning-fast in-memory temporal indexing. Proc. ACM Manag. Data 2(1)
Disk-Based Interval Indexes Under the Increasing Ending Time Assumption (2024). DOI 10.1145/3639275. URL https://doi.org/10. 1145/3639275 12. Costa, D., La Cava, L., Tagarelli, A.: Unraveling the nft economy: A comprehensive collection of non-fungible token transactions and metadata. Data in Brief 51, 109,749 (2023) 13. Cudre-Mauroux, P., Wu, E., Madden, S.: Trajstore: An adaptive storage system for very large trajectory data sets. In: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), pp. 109–120. IEEE (2010) 14. De Almeida, V.T., Güting, R.H.: Indexing the trajectories of moving objects in networks. GeoInformatica 9(1), 33–60 (2005) 15. Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, p. 109–121. Association for Computing Machinery, New York, NY, USA (1986). DOI 10.1145/12130.12142. URL https://doi. org/10.1145/12130.12142 16. Edelsbrunner, H.: Dynamic rectangle intersection searching. Technical Report p. 47 (1980) 17. Elmasri, R., Wuu, G.T.J., Kim, Y.J.: The time index—an access structure for temporal data. In: Proceedings of the Sixteenth International Conference on Very Large Databases, p. 1–12. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1990) 18. Eltabakh, M., Eltarras, R., Aref, W.: Space-partitioning trees in postgresql: Realization and performance. In: 22nd International Conference on Data Engineering (ICDE’06), p. 100–100. IEEE (2006). DOI 10.1109/icde.2006.146. URL http://dx.doi. org/10.1109/ICDE.2006.146 19. Faloutsos, C., Rong, Y.: Dot: A spatial access method using fractals. In: Proceedings of the Seventh International Conference on Data Engineering, p. 152–159. IEEE Computer Society, USA (1991) 20. Gaede, V., Günther, O.: Multidimensional access methods. ACM Comput. Surv. 30(2), 170–231 (1998). DOI 10.1145/280277. 280279. URL https://doi.org/10.1145/280277.280279 21. Goh, C.H., Lu, H., Ooi, B.C., Tan, K.L.: Indexing temporal data using existing b+-trees. Data Knowl. Eng. 18(2), 147–165 (1996). DOI 10.1016/0169-023X(95)00034-P. URL https: //doi.org/10.1016/0169-023X(95)00034-P 22. Hou, Y., Li, J., He, Z., Yan, A., Chen, X., McAuley, J.: Bridging language and items for retrieval and recommendation. arXiv preprint arXiv:2403.03952 (2024) 23. Hu, X., Sintos, S., Gao, J., Agarwal, P.K., Yang, J.: Computing complex temporal join queries efficiently. In: Proceedings of the 2022 International Conference on Management of Data, SIGMOD ’22, p. 2076–2090. Association for Computing Machinery, New York, NY, USA (2022). DOI 10.1145/3514221.3517893. URL https://doi.org/10.1145/3514221.3517893 24. Kanellakis, P.C., Ramaswamy, S., Vengroff, D.E., Vitter, J.S.: Indexing for data models with constraints and classes (extended abstract). In: Proceedings of the Twelfth ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems, PODS ’93, p. 233–243. Association for Computing Machinery, New York, NY, USA (1993). DOI 10.1145/153850.153884. URL https://doi.org/10.1145/153850.153884 25. Kolovson, C.P., Stonebraker, M.: Segment indexes: dynamic indexing techniques for multi-dimensional interval data. SIGMOD Rec. 20(2), 138–147 (1991). DOI 10.1145/119995.115807. URL https://doi.org/10.1145/119995.115807 26. Kriegel, H.P., Pötke, M., Seidl, T.: Managing intervals efficiently in object-relational databases. In: Proceedings of the 26th International Conference on Very Large Data Bases, VLDB ’00, p. 407–418. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2000) 27. Lanka, S., Mays, E.: Fully persistent b+-trees. ACM SIGMOD Record 20(2), 426–435 (1991)
17
28. Lu, W., Zhao, Z., Wang, X., Li, H., Zhang, Z., Shui, Z., Ye, S., Pan, A., Du, X.: A lightweight and efficient temporal database management system in tdsql. Proc. VLDB Endow. 12(12), 2035–2046 (2019). DOI 10.14778/3352063.3352122. URL https://doi. org/10.14778/3352063.3352122 29. Nievergelt, J., Hinrichs, K.: Storage and access structures for geometric data bases. In: Foundations of Data Organization, pp. 441– 455. Springer (1987) 30. Patel, J.M., Chen, Y., Chakka, V.P.: Stripes: an efficient index for predicted trajectories. In: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pp. 635– 646 (2004) 31. Salzberg, B., Tsotras, V.J.: Comparison of access methods for time-evolving data. ACM Comput. Surv. 31(2), 158–221 (1999). DOI 10.1145/319806.319816. URL https://doi.org/10. 1145/319806.319816 32. Seeger, B., Kriegel, H.P.: Techniques for design and implementation of efficient spatial access methods. In: Proceedings of the 14th International Conference on Very Large Data Bases, VLDB ’88, p. 360–371. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1988) 33. Segev, A., Gunadhi, H.: Efficient indexing methods for temporal relations. IEEE Trans. on Knowl. and Data Eng. 5(3), 496–509 (1993). DOI 10.1109/69.224200. URL https://doi.org/10. 1109/69.224200 34. Sellis, T.K., Roussopoulos, N., Faloutsos, C.: The r+-tree: A dynamic index for multi-dimensional objects. In: Proceedings of the 13th International Conference on Very Large Data Bases, VLDB ’87, p. 507–518. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1987) 35. Song, Z., Roussopoulos, N.: Seb-tree: An approach to index continuously moving objects. In: Proceedings of the 4th International Conference on Mobile Data Management, MDM ’03, p. 340–344. Springer-Verlag, Berlin, Heidelberg (2003) 36. U, L.H., Mamoulis, N., Berberich, K., Bedathur, S.: Durable top-k search in document archives. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, p. 555–566. Association for Computing Machinery, New York, NY, USA (2010). DOI 10.1145/1807167.1807228. URL https://doi.org/10.1145/1807167.1807228 37. Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33(2), 209–271 (2001). DOI 10.1145/384192.384193. URL https://doi.org/ 10.1145/384192.384193 38. Wang, L., Zheng, Y., Xie, X., Ma, W.Y.: A flexible spatio-temporal indexing scheme for large-scale gps track retrieval. In: Proceedings of the The Ninth International Conference on Mobile Data Management, MDM ’08, p. 1–8. IEEE Computer Society, USA (2008). DOI 10.1109/MDM.2008.24. URL https://doi.org/ 10.1109/MDM.2008.24