 |
|
|
R-Tree Based Indexing of Now-Relative Bitemporal Data |
Full Paper (PDF)
|
The databases of a wide range of applications, e.g., in data warehousing, store multiple states of time-evolving data.
These databases contain a substantial part of now-relative data: data thatbecame valid at some past time and remains valid until the current time.
More specifically, two temporal aspects of data are frequently of interest, namely valid time, when data is true, and transaction time, when data iscurrent in the database, leading to bitemporal data.
Only little work, based mostly on R-trees, has addressed the indexing of bitemporal data.
No indices exist that contend well with now-relative data, which leads to temporal data regions that are continuous functions of time.
The paper proposes two extended R*-trees that permit the indexing of data regions that grow continuously over time, by also letting the internal bounding regions grow.
Internal bounding regions may be triangular as well as rectangular.
New heuristics for the algorithms that govern the index structure are provided.
As a result, dead space and overlap, now also functions of time, are reduced.
Performance studies indicate that the best extended index is typically 3-5times faster than the existing R-tree based indices.
|
References, where available, link to the DBLP on the World Wide Web.
[Bec90]Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331[Ber97]...
[Cli97]James Clifford, Curtis E. Dyreson, Tomás Isakowitz, Christian S. Jensen, Richard T. Snodgrass:
On the Semantics of ``Now'' in Databases.
TODS 22(2): 171-214(1997)[Dri89]James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan:
Making Data Structures Persistent.
JCSS 38(1): 86-124(1989)[Gut84]Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57[HNP95]Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573[Jag90]H. V. Jagadish:
Linear Clustering of Objects with Multiple Atributes.
SIGMOD Conference 1990: 332-342[JS96]Christian S. Jensen, Richard T. Snodgrass:
Semantics of Time-Varying Information.
IS 21(4): 311-352(1996)[KF94]Ibrahim Kamel, Christos Faloutsos:
Hilbert R-tree: An Improved R-tree using Fractals.
VLDB 1994: 500-509[KTF95]Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos:
Access Methods for Bi-Temporal Databases.
Temporal Databases 1995: 235-254[KTF97]Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos:
Designing Access Methods for Bitemporal Databases.
TKDE 10(1): 1-20(1998)[LL98]Scott T. Leutenegger, Mario A. Lopez:
The Effect of Buffering on the Performance of R-Trees.
ICDE 1998: 164-171[NDE96]Mario A. Nascimento, Margaret H. Dunham, Ramez Elmasri:
M-IVTT: An Index for Bitemporal Databases.
DEXA 1996: 779-790[SA85]Richard T. Snodgrass, Ilsoo Ahn:
A Taxonomy of Time in Databases.
SIGMOD Conference 1985: 236-246[Sam90]Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
[Sno86]Richard T. Snodgrass, Ilsoo Ahn:
Temporal Databases.
IEEE Computer 19(9): 35-42(1986)[Sno87]Richard T. Snodgrass:
The Temporal Query Language TQuel.
TODS 12(2): 247-298(1987)[Sno95]Richard T. Snodgrass (Ed.):
The TSQL2 Temporal Query Language.
Kluwer 1995, ISBN 0-7923-9614-6
Contents[Sno96]...
[Sno96]...
[SRF87]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518[SRF97]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
Multidimensional Access Methods: Trees Have Grown Everywhere.
VLDB 1997: 13-14[ST97]...
|
@inproceedings{DBLP:conf/vldb/BliujuteJSS98,
author = {Rasa Bliujute and
Christian S. Jensen and
Simonas Saltenis and
Giedrius Slivinskas},
editor = {Ashish Gupta and
Oded Shmueli and
Jennifer Widom},
title = {R-Tree Based Indexing of Now-Relative Bitemporal Data},
booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
Large Data Bases, August 24-27, 1998, New York City, New York,
USA},
publisher = {Morgan Kaufmann},
year = {1998},
isbn = {1-55860-566-5},
pages = {345-356},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
