AITTI: Augmented Interval Tree for Temporal Indexing
Open Access
- 24 September 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (4) , 1-28
Abstract
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.Keywords
This publication has 59 references indexed in Scilit:
- Efficient Algorithms for Top-k Stabbing Queries on Weighted Interval Data2024
- What’s New in Temporal Databases?2022
- Temporal Data Management – An Overview2018
- Amortized Bounds for Dynamic Orthogonal Range Reporting2014
- Indexing Temporal Data with Virtual StructureLecture Notes in Computer Science, 2010
- Computational Geometry2008
- SEB-tree: An Approach to Index Continuously Moving Objects2002
- Interval Sequences: An Object-Relational Approach to Manage Spatial Data2001
- Indexing for Data Models with Constraints and ClassesJournal of Computer and System Sciences, 1996
- External segment treesAlgorithmica, 1994