The Snapshot Index: An I/O-Optimal access method for timeslice queries

摘要

We present an access method for timeslice queries that reconstructs a past state s(t) of a time-evolving collection of objects, in O(sollogbn + ¦s(t)¦b) I/O's, where ¦s(t)¦ denotes the size of the collection at time t, n is the total number of changes in the collection's evolution and b is the size of an I/O transfer. Changes include the addition, deletion or attribute modification of objects; they are assumed to occur in increasing time order and always affect the most current state of the collection (thus our index supports transaction-time.) The space used is O(nb) while the update processing is constant per change, i.e., independent of n. This is the first I/O-optimal access method for this problem using O(nb) space and O(1) updating (in the expected amortized sense due to the use of hashing.) This performance is also achieved for interval intersection temporal queries. An advantage of our approach is that its performance can be tuned to match particular application needs (trading space for query time and vice versa). In addition, the Snapshot Index can naturally migrate data on a write-once optical medium while maintaining the same performance bounds.