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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD DiSC

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/Disc99_1 or /cdrom

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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
[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)
[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)
[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. Inf. Syst. 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. IEEE Trans. Knowl. Data Eng. 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. ACM Trans. Database Syst. 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]: ...