The Time Index+ : An Incremental Access Structure for Temporal Databases

Abstract

In this paper, we propose a new indexing structure, called the Time Index+, which extends the incremental structure technique introduced in the Time Index [ElWK90, ElKG93]. The Time Index performs well for data that often overlaps and has a non-- uniform distribution. However, it requires huge amounts of storage and suffers from degradation in update performance. The Time Index+ overcomes the deficiencies of the Time Index by proposing an efficient new storage model for partitioning logical buckets and by suggesting a graceful new method for handling object versions with long and very long time intervals.<P>We validate our claims for the efficiency of our new techniques by analyzing and, comparing four indexing structures: the Time Index$^{+}$, the Time Index, the, Packed R--Tree~[RoLe85, KaFa93], and the Parameterized R--Tree. Our simulation identifies important parameters, and shows how they affect the performance of the four considered indexing structures. These include mean of version lifespan, block size, query time interval length, and total number of versions. Our simulation results show that: (1) The Time Index+ requires on average 60% less storage than the the Time Index but 50% more storage than the Packed R--Tree and the Parameterized R--Tree and (2) the Time Index+ provides an improvement in search time of 10% over the Time Index, of an order of magnitude over the Packed R--Tree, and of at least 100% over the Parameterized R--Tree.