Efficient Archivable Time Index: A Dynamic Indexing Scheme for Temporal Data

We present a practical and asymptotically optimal indexing structure for a versioned timestamped database with step-wise constant data. Three version operations, insertions, updates, and deletes are allowed for the present version, whereas query operations are allowed for any version, present or past. Snapshot and time-range queries can be answered optimally with this structure. As a two-level index, attribute-search and attribute-history queries can be solved in time proportional to the output size plus an additive logarithmic term. The time index uses linear storage; this improves upon previous work which either had logarithmic query overhead time and quadratic space, or linear space and linear query overhead time. The tradeoff is a small increase in the time for version operations from constant to logarithmic. All measures are worst-case. The index has a natural structure for archiving in write-once storage media like optical disks