TIDE: Indexing Time Intervals by Duration and Endpoint

Indexes for large collections of intervals are common in temporal databases, where each record has a lifespan, or validity interval.We propose a universal representation that encapsulates various interval indexes using diagonal corner structures, providing valuable insights about their effectiveness.Moreover, we exploit our findings to develop TIDE, a disk-based index for historical intervals.TIDE adopts a two-level architecture.A top tree organizes intervals by their duration.The leaf nodes of the top tree 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.An experimental evaluation with real data sets shows that TIDE achieves impressive performance gains with respect to its direct competitor, on insertion (up to x100) and query processing (up to x7000) speed.