AITTI: Augmented Interval Tree for Temporal Indexing

Querying temporal and versioned data is a classic problem that has been studied for more than four decades. In a temporal database, a record version is characterized by a temporal validity interval. Queries on temporal databases retrieve record versions that were valid at a time point or sometime within a time interval and satisfy a selection predicate on some object attribute. There is little recent work on indexing temporal data for queries with range filters on a given attribute, especially considering modern commodity hardware. We revisit this classic problem by proposing AITTI, an in-memory index, which uses an interval tree as a backbone to index the time dimension. The record versions in each interval tree node are organized by a new data structure tailored for open-ended range queries in the time-attribute domain. We theoretically analyze the search and update performance of AITTI and its component structures. We experimentally show the superiority of our index over previous work on real data.