Disk-Based Interval Indexes Under the Increasing Ending Time Assumption
2026-06-22 • Databases
Databases
AI summaryⓘ
The authors study how to organize and search through large lists of time intervals, like when things start and end. They show that you can think of these intervals as points in a 2D space to better find which groups definitely or might contain answers to queries. They create two new index systems called CEB and TIDE that store intervals using their center, endpoint, or duration, making it easier and faster to add new intervals and search through them. Compared to older methods, their approaches use less space and speed up inserts, with TIDE also improving query speed significantly.
interval indextemporal databases2D corner structureB+-treeappend-only indexinterval centerinterval endpointinterval durationquery processingdisk-based index
Authors
Kai Wang, Moin Hussian Moti, Dimitris Papadias
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.