dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems.

Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601
@inproceedings{DBLP:conf/vldb/SeegerK90,
  author    = {Bernhard Seeger and
               Hans-Peter Kriegel},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {The Buddy-Tree: An Efficient and Robust Access Method for Spatial
               Data Base Systems},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {590-601},
  ee        = {http://www.vldb.org/conf/1990/P590.PDF},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we propose a new multidimensional access method, called the buddy-tree, to support point as well as spatial data in a dynamic environment. The buddy-tree can be seen as a compromise of the R-tree and the grid file, but it is fundamentally different from each of them. Because grid files loose performance for highly correlated data, the buddy-tree is designed to organize such data very efficiently, partitioning only such parts of the data space which contain data and not partitioning empty data space. The directory consists of a very flexible partitioning and reorganization scheme based on a generalization of the buddy-system. As for B-trees, the buddy-tree fulfills the property that insertions and deletions are restricted to exactly one path of the directory. Additional important properties which are not fulfilled in this combination byany other multidimensional tree-based access method are: (i) the directory grows linear in the number of records, (ii) no overflow pages are allowed, (iii) the data space is partitioned into minimum bounding rectangles of the actual data and (iv) the performance is basicly independent of the sequence of insertions. In this paper, we introduce the principles of the buddy-tree, the organizationof its directory and the most important algorithms. Using our standardized testbed, we present a performance comparison of the buddy-tree with other access methods demonstrating the superiority and robustnessof the buddy-tree.

Copyright © 1990 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.


Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BKSS90]
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
[BM72]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bur83]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FSR87]
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fre87]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 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
[HCKW90]
Eric N. Hanson, Moez Chaabouni, Chang-Ho Kim, Yu-Wang Wang: A Predicate Matching Algorithm for Database Rule Systems. SIGMOD Conference 1990: 271-280 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hin85]
...
[HSW88]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kri84]
Hans-Peter Kriegel: Performance Comparison of Index Structures for Multi-Key Retrieval. SIGMOD Conference 1984: 186-196 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS86]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS88]
Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS89]
...
[KSSS89]
Hans-Peter Kriegel, Michael Schiwietz: Performance Comparison of Point and Spatial Access Methods. SSD 1989: 89-114 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LS89]
David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NHS84]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ore82]
Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OM84]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oto84]
Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oto86]
Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ouk85]
Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rob81]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[See89]
...
[SK88]
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tam82]
Markku Tamminen: The Extendible Cell Method for Closest Point Problems. BIT 22(1): 27-41(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WK85]
...

Last update Mon Sep 17 22:00:48 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page