Comparison of access methods for time-evolving data

This paper compares different indexing techniques proposed for supporting e fficient access to temporal data. The comparison is based on a collection o f important performance criteria, including the space consumed, update proc essing, and query time for representative queries. The comparison is based on worst-case analysis, hence no assumptions on data distribution or query frequencies are made. When a number of methods have the same asymptotic wor st-case behavior, features in the methods that affect average case behavior are discussed. Additional criteria examined are the pagination of an index , the ability to cluster related data together, and the ability to efficien tly separate old from current data (so that larger archival storage media s uch as write-once optical disks can be used). The purpose of the paper is t o identify the difficult problems in accessing temporal data and describe h ow the different methods aim to solve them. A general lower bound for answe ring basic temporal queries is also introduced.