pith. sign in

arxiv: 2606.22773 · v1 · pith:LH72JBAYnew · submitted 2026-06-22 · 💻 cs.DB

Disk-Based Interval Indexes Under the Increasing Ending Time Assumption

Kai Wang , Moin Hussian Moti , Dimitris Papadias This is my paper

Pith reviewed 2026-06-26 06:47 UTC · model grok-4.3

classification 💻 cs.DB
keywords interval indexestemporal databasesdisk-based indexesB+-treesincreasing ending timequery processingindex sizeappend-only structures
0
0 comments X

The pith

Under the assumption that intervals arrive in increasing end-time order, two new disk-based indexes achieve smaller size, faster insertions, and quicker queries than prior methods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that interval indexes map to corner structures in 2D space, which distinguishes nodes guaranteed to hold query answers from those that might. Exploiting the increasing ending time arrival order, it builds CEB (center-endpoint) and TIDE (duration-endpoint) indexes as two-layer append-only B+-trees. The top layer orders intervals by center or duration; its leaves anchor bottom-layer trees ordered by endpoint. This yields compact storage and efficient appends, with TIDE delivering the strongest query gains. Readers care because temporal databases routinely store and query large lifespan collections where storage and lookup costs matter directly.

Core claim

By mapping intervals to 2D corner representations and enforcing the increasing ending time arrival order, the two-layer append-only B+-tree indexes CEB and TIDE deliver smaller index sizes, faster insertions, and faster query processing than existing competitors, with TIDE sometimes faster by orders of magnitude.

What carries the argument

Two-layer append-only B+-tree architecture in which the leaf nodes of a top tree (ordering by center or duration) serve as roots of bottom trees (ordering by endpoint).

If this is right

  • Temporal databases can store larger interval collections within the same disk budget.
  • High-rate interval arrivals incur lower insertion latency.
  • Range and point queries on lifespans complete with fewer disk accesses.
  • The corner-space view lets query processors skip entire subtrees that cannot contain answers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same two-layer append-only design could apply to other monotonically ordered streams such as sensor readings or versioned records.
  • Hybrid indexes might combine the IET assumption with additional ordering constraints to further reduce node fan-out.
  • The corner representation offers a general template for turning any interval workload into a pair of 1D ordering problems.
  • If the IET assumption holds only approximately, a small buffer or reordering layer could restore most of the reported gains.

Load-bearing premise

Intervals arrive in order of increasing ending time.

What would settle it

Run the same insertion and query workloads with intervals presented out of increasing-ending-time order and check whether CEB and TIDE lose their reported size and speed advantages over the prior indexes.

Figures

Figures reproduced from arXiv: 2606.22773 by Dimitris Papadias, Kai Wang, Moin Hussian Moti.

Figure 1
Figure 1. Figure 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 unify￾ing framework. Section 4 and Section 5 present the insertion and query processing … view at source ↗
Figure 2
Figure 2. Figure 2: Period-index 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: HINT partitions and stores each interval in multiple nodes. Specif￾ically, 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 exam￾ple, in Figure 1b, interval s7 = [2,23) is stored in n4, n12, n18 and n L 23, where L (R) denotes left (right) leaf node. Due to replication, the seg… view at source ↗
Figure 4
Figure 4. Figure 4: Relational interval-tree timestamps. The append only-tree (AP-tree) [33] orders in￾tervals 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,… view at source ↗
Figure 8
Figure 8. Figure 8: a 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… view at source ↗
Figure 7
Figure 7. Figure 7: Midpoint transformation The start/end timestamp B-tree (SEB) [35] applies cor￾ner structures for indexing intervals following the IET as￾sumption: 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… view at source ↗
Figure 10
Figure 10. Figure 10: Corner structure of the segment-tree 0 4 8 12 16 20 24 28 4 8 12 16 20 24 28 4 8 12 16 20 24 28 32 32 32 (a) the structure 0 4 8 12 16 20 24 28 4 8 12 16 20 24 28 4 8 12 16 20 24 28 32 32 32 (b) query with range [10,13] [PITH_FULL_IMAGE:figures/full_fig_p006_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Corner structure of HINT node is fully covered by s7. The last partition containing te of s7 is stored in leaf node n L 23. 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 n L 23 = [21,23). Internal nodes are mapped to points because they only store intervals covering their full range. A query with range [10,… view at source ↗
Figure 12
Figure 12. Figure 12: Corner structure of the period-index ets with the same parent, if they partially intersect an inter￾val (as opposed to fully intersect in the segment-tree). Each internal bucket is represented as a square in Figure 11a), in￾stead 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… view at source ↗
Figure 14
Figure 14. Figure 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 top tree is ordered by the center point (c = ts+te 2 ) of inter￾vals. 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 t… view at source ↗
Figure 15
Figure 15. Figure 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: … view at source ↗
Figure 16
Figure 16. Figure 16: Range query [qs ,qe] in CEB 4.2 Range Queries Given a range query q = [qs ,qe], CEB returns intervals ful￾filling constraints ts = 2c − te ≤ qe (slash boundary) and te ≥ qs (horizontal boundary). Notably, the query searches bottom trees with center points in [ qs 2 , qe+now 2 ], which cor￾responds to the green area in [PITH_FULL_IMAGE:figures/full_fig_p010_16.png] view at source ↗
Figure 17
Figure 17. Figure 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, in￾tervals 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 simila… view at source ↗
Figure 18
Figure 18. Figure 18: Insertions in TIDE [PITH_FULL_IMAGE:figures/full_fig_p011_18.png] view at source ↗
Figure 19
Figure 19. Figure 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… view at source ↗
Figure 20
Figure 20. Figure 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… view at source ↗
Figure 21
Figure 21. Figure 21: Number of data nodes per bottom tree depending on the dataset, compared to SEB. The index size is dominated by the data nodes in most cases. The only ex￾ception 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. Further￾more, each root of the mutable BTs contains only a handful of data node entries… view at source ↗
Figure 22
Figure 22. Figure 22: I/O cost of inserting the full dataset This leads to fewer BTs on irregular, compared to regular datasets. 6.2 Insertion Performance [PITH_FULL_IMAGE:figures/full_fig_p014_22.png] view at source ↗
Figure 23
Figure 23. 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 num￾ber 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… view at source ↗
Figure 24
Figure 24. Figure 24: Count queries 7 Conclusion Under the IET assumption, intervals are inserted in increas￾ing 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 bot￾tom trees organize intervals on te. We first propose CEB, as an optimization of SEB, which reduces the index size. The top tree of CEB organiz… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims that under the Increasing Ending Time (IET) assumption, interval indexes can be represented via corner structures in 2D space. It introduces CEB (center-endpoint) and TIDE (duration-endpoint) as two-layer disk-based indexes using append-only B+-trees, achieving compact size and fast insertions; TIDE additionally provides faster query processing than competitors, sometimes by orders of magnitude.

Significance. If the IET assumption is realistic for target workloads, the two-layer append-only design and corner-based query optimization could yield practical gains in storage and performance for temporal databases. The explicit exploitation of arrival order for append-only structures is a clear technical contribution when the assumption holds.

major comments (1)
  1. [Abstract] Abstract: All claimed advantages (compact size via append-only B+-trees, fast insertions, TIDE query speed) are derived from the strictly increasing ending-time arrival order. The manuscript does not quantify how often real interval collections satisfy IET or test performance under mild violations, which is load-bearing for the practical significance of the results.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the dependence of our results on the IET assumption. We address this point directly below and will revise the manuscript accordingly to better scope the claims.

read point-by-point responses

  1. Referee: [Abstract] Abstract: All claimed advantages (compact size via append-only B+-trees, fast insertions, TIDE query speed) are derived from the strictly increasing ending-time arrival order. The manuscript does not quantify how often real interval collections satisfy IET or test performance under mild violations, which is load-bearing for the practical significance of the results.

    Authors: We agree that the reported advantages of CEB and TIDE are predicated on the IET assumption, which is stated in the title, abstract, and throughout the paper. The work targets workloads (e.g., append-only temporal logs and event streams) where ending times are non-decreasing upon arrival; the two-layer append-only B+-tree design and corner-based pruning are direct consequences of this ordering. We will revise the abstract to foreground this scope more explicitly. On quantification, the manuscript does not contain a broad empirical survey of real interval collections, as our focus is the algorithmic exploitation of IET when it holds. We will add a dedicated discussion subsection on the assumption's prevalence in targeted domains and the expected behavior under mild violations (performance would fall back toward that of a standard B+-tree without the append-only optimizations). We did not evaluate non-IET workloads because the indexes are specialized for the IET case; such experiments would require a different design. revision: partial

Circularity Check

0 steps flagged

No circularity; constructions are conditional on external IET assumption

full rationale

The paper defines CEB and TIDE as two-layer append-only B+-tree indexes whose compactness and insertion efficiency are explicitly derived from the stated IET arrival assumption rather than from any self-referential equation, fitted parameter renamed as prediction, or self-citation chain. No equations appear in the abstract or description that reduce claimed performance metrics to the paper's own outputs by construction. The IET premise is presented as an input assumption whose real-world prevalence is outside the derivation; this is a modeling choice, not a circular reduction. The central claims therefore remain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claims rest on the IET arrival assumption and the proposed corner-based two-layer B+-tree organizations; no free parameters or invented physical entities are described.

axioms (1)
  • domain assumption Intervals arrive in order of increasing ending time (IET)
    This ordering assumption is invoked to justify the compact size and efficient insertion properties of the append-only trees.
invented entities (2)
  • CEB index no independent evidence
    purpose: Two-layer index in corner space defined by interval center and endpoint
    New structure introduced to organize intervals under IET.
  • TIDE index no independent evidence
    purpose: Two-layer index organizing intervals by duration and endpoint
    New structure introduced to organize intervals under IET.

pith-pipeline@v0.9.1-grok · 5747 in / 1317 out tokens · 23878 ms · 2026-06-26T06:47:12.038478+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 22 canonical work pages

  1. [1]

    Sketches-based join size estimation under local differential privacy

    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

    work page doi:10.1109/icde60146.2024 2024

  2. [2]

    In: Proceedings of 37th Conference on Foun- dations of Computer Science, pp

    Arge, L., Vitter, J.: Optimal dynamic interval management in ex- ternal memory. In: Proceedings of 37th Conference on Foun- dations of Computer Science, pp. 560–569. IEEE Comput. Soc. Press (1996). DOI 10.1109/SFCS.1996.548515

    work page doi:10.1109/sfcs.1996.548515 1996

  3. [3]

    SIGMOD Rec.19(2), 322–331 (1990)

    Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The r*- tree: an efficient and robust access method for points and rectan- gles. SIGMOD Rec.19(2), 322–331 (1990). DOI 10.1145/93605. 98741. URLhttps://doi.org/10.1145/93605.98741

    work page doi:10.1145/93605 1990

  4. [4]

    In: Proceedings of the 16th Inter- national Symposium on Spatial and Temporal Databases, SSTD ’19, p

    Behrend, A., Dign ¨os, A., Gamper, J., Schmiegelt, P., V oigt, H., Rottmann, M., Kahl, K.: Period index: A learned 2d hash index for range and duration queries. In: Proceedings of the 16th Inter- national Symposium on Spatial and Temporal Databases, SSTD ’19, p. 100–109. Association for Computing Machinery, New York, NY , USA (2019). DOI 10.1145/3340964.3...

    work page doi:10.1145/3340964.3340965 2019

  5. [5]

    Berg, M.d., Cheong, O., Kreveld, M.v., Overmars, M.: Compu- tational Geometry: Algorithms and Applications, 3rd ed. edn. Springer-Verlag TELOS, Santa Clara, CA, USA (2008)

    2008

  6. [6]

    IEEE Transactions on Knowledge and Data Engineering (2025)

    Bouros, P., Christodoulou, G., Rauch, C., Titkov, A., Mamoulis, N.: Querying interval data on steroids. IEEE Transactions on Knowledge and Data Engineering (2025)

    2025

  7. [7]

    The VLDB Journal30(4), 667–691 (2021)

    Bouros, P., Mamoulis, N., Tsitsigkos, D., Terrovitis, M.: In- memory interval joins. The VLDB Journal30(4), 667–691 (2021). DOI 10.1007/s00778-020-00639-0. URLhttps://doi.org/ 10.1007/s00778-020-00639-0

    work page doi:10.1007/s00778-020-00639-0 2021

  8. [8]

    In: Proceedings of the 55th An- nual ACM Symposium on Theory of Computing, STOC 2023, p

    Brodal, G.S., Rysgaard, C.M., Svenning, R.: External memory fully persistent search trees. In: Proceedings of the 55th An- nual 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. URLhttps: //doi.org/10.1145/3564246.3585140

    work page doi:10.1145/3564246.3585140 2023

  9. [9]

    In: Pro- ceedings of the 35th International Conference on Scientific and Statistical Database Management, SSDBM ’23

    Ceccarello, M., Dign ¨os, A., Gamper, J., Khnaisser, C.: Index- ing temporal relations for range-duration queries. In: Pro- ceedings 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. URLhttps://doi.org/10.1145/ 3603...

    work page doi:10.1145/3603719.3603732 2023

  10. [10]

    In: Proceedings of the 2022 International Conference on Management of Data, SIGMOD ’22, p

    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. URLhttps: //doi.org/10.1145/3514221.3517873

    work page doi:10.1145/3514221.3517873 2022

  11. [11]

    Christodoulou, G., Bouros, P., Mamoulis, N.: Lit: Lightning-fast in-memory temporal indexing. Proc. ACM Manag. Data2(1) Disk-Based Interval Indexes Under the Increasing Ending Time Assumption 17 (2024). DOI 10.1145/3639275. URLhttps://doi.org/10. 1145/3639275

    work page doi:10.1145/3639275 2024

  12. [12]

    Data in Brief51, 109,749 (2023)

    Costa, D., La Cava, L., Tagarelli, A.: Unraveling the nft econ- omy: A comprehensive collection of non-fungible token transac- tions and metadata. Data in Brief51, 109,749 (2023)

    2023

  13. [13]

    In: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), pp

    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)

    2010

  14. [14]

    GeoInformatica9(1), 33–60 (2005)

    De Almeida, V .T., G¨uting, R.H.: Indexing the trajectories of mov- ing objects in networks. GeoInformatica9(1), 33–60 (2005)

    2005

  15. [15]

    In: Proceedings of the Eighteenth An- nual ACM Symposium on Theory of Computing, STOC ’86, p

    Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. In: Proceedings of the Eighteenth An- nual 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. URLhttps://doi. org/10.1145/12130.12142

    work page doi:10.1145/12130.12142 1986

  16. [16]

    Technical Report p

    Edelsbrunner, H.: Dynamic rectangle intersection searching. Technical Report p. 47 (1980)

    1980

  17. [17]

    In: Proceedings of the Sixteenth In- ternational Conference on Very Large Databases, p

    Elmasri, R., Wuu, G.T.J., Kim, Y .J.: The time index—an access structure for temporal data. In: Proceedings of the Sixteenth In- ternational Conference on Very Large Databases, p. 1–12. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1990)

    1990

  18. [18]

    In: 22nd International Conference on Data Engineering (ICDE’06), p

    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. URLhttp://dx.doi. org/10.1109/ICDE.2006.146

    work page doi:10.1109/icde.2006.146 2006

  19. [19]

    In: Proceedings of the Seventh International Conference on Data Engineering, p

    Faloutsos, C., Rong, Y .: Dot: A spatial access method using frac- tals. In: Proceedings of the Seventh International Conference on Data Engineering, p. 152–159. IEEE Computer Society, USA (1991)

    1991

  20. [20]

    ACM Comput

    Gaede, V ., G¨unther, O.: Multidimensional access methods. ACM Comput. Surv.30(2), 170–231 (1998). DOI 10.1145/280277. 280279. URLhttps://doi.org/10.1145/280277.280279

    work page doi:10.1145/280277 1998

  21. [21]

    Data Knowl

    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. URLhttps: //doi.org/10.1016/0169-023X(95)00034-P

    work page doi:10.1016/0169-023x(95)00034-p 1996

  22. [22]

    arXiv preprint arXiv:2403.03952 (2024)

    Hou, Y ., Li, J., He, Z., Yan, A., Chen, X., McAuley, J.: Bridg- ing language and items for retrieval and recommendation. arXiv preprint arXiv:2403.03952 (2024)

    Pith/arXiv arXiv 2024

  23. [23]

    In: Proceedings of the 2022 International Conference on Management of Data, SIGMOD ’22, p

    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

    work page doi:10.1145/3514221.3517893 2022

  24. [24]

    In: Proceedings of the Twelfth ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, PODS ’93, p

    Kanellakis, P.C., Ramaswamy, S., Vengroff, D.E., Vitter, J.S.: In- dexing for data models with constraints and classes (extended ab- stract). In: Proceedings of the Twelfth ACM SIGACT-SIGMOD- SIGART 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. ...

    work page doi:10.1145/153850.153884 1993

  25. [25]

    SIGMOD Rec.20(2), 138–147 (1991)

    Kolovson, C.P., Stonebraker, M.: Segment indexes: dynamic in- dexing 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

    work page doi:10.1145/119995.115807 1991

  26. [26]

    In: Proceedings of the 26th Inter- national Conference on Very Large Data Bases, VLDB ’00, p

    Kriegel, H.P., P ¨otke, M., Seidl, T.: Managing intervals efficiently in object-relational databases. In: Proceedings of the 26th Inter- national Conference on Very Large Data Bases, VLDB ’00, p. 407–418. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2000)

    2000

  27. [27]

    ACM SIGMOD Record20(2), 426–435 (1991)

    Lanka, S., Mays, E.: Fully persistent b+-trees. ACM SIGMOD Record20(2), 426–435 (1991)

    1991

  28. [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 man- agement system in tdsql. Proc. VLDB Endow.12(12), 2035–2046 (2019). DOI 10.14778/3352063.3352122. URLhttps://doi. org/10.14778/3352063.3352122

    work page doi:10.14778/3352063.3352122 2035

  29. [29]

    In: Foundations of Data Organization, pp

    Nievergelt, J., Hinrichs, K.: Storage and access structures for geo- metric data bases. In: Foundations of Data Organization, pp. 441–

  30. [30]

    In: Proceedings of the 2004 ACM SIG- MOD international conference on Management of data, pp

    Patel, J.M., Chen, Y ., Chakka, V .P.: Stripes: an efficient index for predicted trajectories. In: Proceedings of the 2004 ACM SIG- MOD international conference on Management of data, pp. 635– 646 (2004)

    2004

  31. [31]

    ACM Comput

    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. URLhttps://doi.org/10. 1145/319806.319816

    work page doi:10.1145/319806.319816 1999

  32. [32]

    In: Proceedings of the 14th International Conference on Very Large Data Bases, VLDB ’88, p

    Seeger, B., Kriegel, H.P.: Techniques for design and implementa- tion 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)

    1988

  33. [33]

    IEEE Trans

    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. URLhttps://doi.org/10. 1109/69.224200

    work page doi:10.1109/69.224200 1993

  34. [34]

    In: Proceedings of the 13th International Conference on Very Large Data Bases, VLDB ’87, p

    Sellis, T.K., Roussopoulos, N., Faloutsos, C.: The r+-tree: A dy- namic 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 Fran- cisco, CA, USA (1987)

    1987

  35. [35]

    In: Proceedings of the 4th International Conference on Mobile Data Management, MDM ’03, p

    Song, Z., Roussopoulos, N.: Seb-tree: An approach to index con- tinuously moving objects. In: Proceedings of the 4th International Conference on Mobile Data Management, MDM ’03, p. 340–344. Springer-Verlag, Berlin, Heidelberg (2003)

    2003

  36. [36]

    In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIG- MOD ’10, p

    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, SIG- MOD ’10, p. 555–566. Association for Computing Machinery, New York, NY , USA (2010). DOI 10.1145/1807167.1807228. URLhttps://doi.org/10.1145/1807167.1807228

    work page doi:10.1145/1807167.1807228 2010

  37. [37]

    ACM Comput

    Vitter, J.S.: External memory algorithms and data structures: deal- ing with massive data. ACM Comput. Surv.33(2), 209–271 (2001). DOI 10.1145/384192.384193. URLhttps://doi.org/ 10.1145/384192.384193

    work page doi:10.1145/384192.384193 2001

  38. [38]

    In: Proceed- ings of the The Ninth International Conference on Mobile Data Management, MDM ’08, p

    Wang, L., Zheng, Y ., Xie, X., Ma, W.Y .: A flexible spatio-temporal indexing scheme for large-scale gps track retrieval. In: Proceed- ings 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. URLhttps://doi.org/ 10.1109/MDM.2008.24

    work page doi:10.1109/mdm.2008.24 2008