ACM SIGMOD Anthology VLDB dblp.uni-trier.de

R-Tree Based Indexing of Now-Relative Bitemporal Data.

Rasa Bliujute, Christian S. Jensen, Simonas Saltenis, Giedrius Slivinskas: R-Tree Based Indexing of Now-Relative Bitemporal Data. VLDB 1998: 345-356
@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},
  ee        = {db/conf/vldb/BliujuteJSS98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

Copyright © 1998 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ber97]
...
[Cli97]
James Clifford, Curtis E. Dyreson, Tomás Isakowitz, Christian S. Jensen, Richard T. Snodgrass: On the Semantics of "Now" in Databases. ACM Trans. Database Syst. 22(2): 171-214(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dri89]
James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38(1): 86-124(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HNP95]
Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jag90]
H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JS96]
Christian S. Jensen, Richard T. Snodgrass: Semantics of Time-Varying Information. Inf. Syst. 21(4): 311-352(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KF94]
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KTF95]
Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Access Methods for Bi-Temporal Databases. Temporal Databases 1995: 235-254 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KTF97]
Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Designing Access Methods for Bitemporal Databases. IEEE Trans. Knowl. Data Eng. 10(1): 1-20(1998) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LL98]
Scott T. Leutenegger, Mario A. Lopez: The Effect of Buffering on the Performance of R-Trees. ICDE 1998: 164-171 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NDE96]
Mario A. Nascimento, Margaret H. Dunham, Ramez Elmasri: M-IVTT: An Index for Bitemporal Databases. DEXA 1996: 779-790 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SA85]
Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sam90]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno86]
Richard T. Snodgrass, Ilsoo Ahn: Temporal Databases. IEEE Computer 19(9): 35-42(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno87]
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno95]
Richard T. Snodgrass (Ed.): The TSQL2 Temporal Query Language. Kluwer 1995, ISBN 0-7923-9614-6
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno96]
...
[Sno96]
...
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF97]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: Multidimensional Access Methods: Trees Have Grown Everywhere. VLDB 1997: 13-14 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ST97]
...

Copyright © Tue Mar 16 02:22:07 2010 by Michael Ley (ley@uni-trier.de)