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(log(b) n + \s(t)\/b) I/O's, where \s(t)\ denotes the size of the collection a t time t, n is the total number of changes in the collection's evoluti on and b is the size of an I/O transfer. Changes include the addition, deletion or attribute modification of objects; they are assumed to oc cur in increasing time order and always affect the most current state of the collection (thus our index supports transaction-time.) The spac e used is O(n/b) 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(n/b) space and O(1) updating (in the expected am ortized sense due to the use of hashing.) This performance is also ach ieved for interval intersection temporal. queries. An advantage of our approach is that its performance can be tuned to match particular app lication needs (trading space for query time and vice versa). In addit ion, the Snapshot Index can naturally migrate data on a write-once opt ical medium while maintaining the same performance bounds.