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

dc.contributor.authorKouramajian, Vramen_US
dc.contributor.authorKamel, Ibrahimen_US
dc.contributor.authorElmasri, Ramezen_US
dc.contributor.authorWaheed, Syeden_US
dc.description.abstractIn 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.en_US
dc.format.extent1019026 bytes
dc.relation.ispartofseriesISR; TR 1994-18en_US
dc.subjectdata structuresen_US
dc.subjectSystems Integrationen_US
dc.titleThe Time Index+ : An Incremental Access Structure for Temporal Databasesen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
995.14 KB
Adobe Portable Document Format