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 = {db/conf/vldb/SeegerK90.html},
crossref = {DBLP:conf/vldb/90},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
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
BibTeX
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 BibTeX
- [BM72]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indices.
Acta Inf. 1: 173-189(1972) BibTeX
- [Bur83]
- Walter A. Burkhard:
Interpolation-Based Index Maintenance.
BIT 23(3): 274-294(1983) BibTeX
- [FSR87]
- Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos:
Analysis of Object Oriented Spatial Access Methods.
SIGMOD Conference 1987: 426-439 BibTeX
- [Fre87]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269 BibTeX
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [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 BibTeX
- [Hin85]
- ...
- [HSW88]
- Andreas Hutflesz, Hans-Werner Six, Peter Widmayer:
Twin Grid Files: Space Optimizing Access Schemes.
SIGMOD Conference 1988: 183-190 BibTeX
- [Kri84]
- Hans-Peter Kriegel:
Performance Comparison of Index Structures for Multi-Key Retrieval.
SIGMOD Conference 1984: 186-196 BibTeX
- [KS86]
- Hans-Peter Kriegel, Bernhard Seeger:
Multidimensional Order Preserving Linear Hashing with Partial Expansions.
ICDT 1986: 203-220 BibTeX
- [KS88]
- Hans-Peter Kriegel, Bernhard Seeger:
PLOP-Hashing: A Grid File without Directory.
ICDE 1988: 369-376 BibTeX
- [KS89]
- ...
- [KSSS89]
- Hans-Peter Kriegel, Michael Schiwietz:
Performance Comparison of Point and Spatial Access Methods.
SSD 1989: 89-114 BibTeX
- [LS89]
- David B. Lomet, Betty Salzberg:
A Robust Multi-Attribute Search Structure.
ICDE 1989: 296-304 BibTeX
- [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) BibTeX
- [Ore82]
- Jack A. Orenstein:
Multidimensional Tries Used for Associative Searching.
Inf. Process. Lett. 14(4): 150-157(1982) BibTeX
- [OM84]
- Jack A. Orenstein, T. H. Merrett:
A Class of Data Structures for Associative Searching.
PODS 1984: 181-190 BibTeX
- [Oto84]
- Ekow J. Otoo:
A Mapping Function for the Directory of a Multidimensional Extendible Hashing.
VLDB 1984: 493-506 BibTeX
- [Oto86]
- Ekow J. Otoo:
Balanced Multidimensional Extendible Hash Tree.
PODS 1986: 100-113 BibTeX
- [Ouk85]
- Aris M. Ouksel:
The Interpolation-Based Grid File.
PODS 1985: 20-27 BibTeX
- [Rob81]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18 BibTeX
- [See89]
- ...
- [SK88]
- Bernhard Seeger, Hans-Peter Kriegel:
Techniques for Design and Implementation of Efficient Spatial Access Methods.
VLDB 1988: 360-371 BibTeX
- [Tam82]
- Markku Tamminen:
The Extendible Cell Method for Closest Point Problems.
BIT 22(1): 27-41(1982) BibTeX
- [WK85]
- ...
Referenced by
- Ke Wang, Beng Chin Ooi, Sam Yuan Sung:
P-Tree: A B-Tree Index for Lists.
DASFAA 1999: 221-228
- Miyeon Kim, Sumi Lim, Jangsu Kim:
Development of Multi-step Filtering Processor.
DASFAA 1999: 169-176
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Gísli R. Hjaltason, Hanan Samet:
Incremental Distance Join Algorithms for Spatial Databases.
SIGMOD Conference 1998: 237-248
- Andreas Henrich:
The LSDh-Tree: An Access Structure for Feature Vectors.
ICDE 1998: 362-369
- Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft:
Compressing Relations and Indexes.
ICDE 1998: 370-379
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
Using Extended Feature Objects for Partial Similarity Retrieval.
VLDB J. 6(4): 333-348(1997)
- Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song:
A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations.
VLDB 1997: 416-425
- Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer:
A Generic Approach to Bulk Loading Multidimensional Index Structures.
VLDB 1997: 406-415
- Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, Jie-Bing Yu:
Processing Queries By Linear Constraints.
PODS 1997: 257-267
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39
- Bernd-Uwe Pagel, Hans-Werner Six:
Are Window Queries Representative for Arbitrary Range Queries?
PODS 1996: 150-160
- Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai:
Efficient Search of Multi-Dimensional B-Trees.
VLDB 1995: 710-719
- Michael Freeston:
A General Solution of the n-dimensional B-tree Problem.
SIGMOD Conference 1995: 80-91
- Ralf Hartmut Güting:
An Introduction to Spatial Database Systems.
VLDB J. 3(4): 357-399(1994)
- Christoph Kilger, Guido Moerkotte:
Indexing Multiple Sets.
VLDB 1994: 180-191
- Thomas Brinkhoff, Hans-Peter Kriegel:
The Impact of Global Clustering on Spatial Database Systems.
VLDB 1994: 168-179
- Hongjun Lu, Beng Chin Ooi:
Spatial Indexing: Past and Future.
IEEE Data Eng. Bull. 16(3): 16-21(1993)
- Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer:
Towards an Analysis of Range Query Performance in Spatial Data Structures.
PODS 1993: 214-221
- Rajiv Mehrotra, James E. Gary:
Feature-Based Retrieval of Similar Shapes.
ICDE 1993: 108-115
- Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider:
Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems.
ICDE 1993: 40-49
- Jui-Tine Lee, Geneva G. Belford:
An Efficient Object-based Algorithm for Spatial Searching, Insertion and Deletion.
ICDE 1992: 40-47
- Amarnath Gupta, Terry E. Weymouth, Ramesh Jain:
Semantic Queries with Pictures: The VIMSYS Model.
VLDB 1991: 69-79
- Bernhard Seeger, Per-Åke Larson:
Multi-Disk B-trees.
SIGMOD Conference 1991: 436-445
- Leonore Neugebauer:
Optimization and Evaluation of Database Queries Including Embedded Interpolation Procedures.
SIGMOD Conference 1991: 118-127
- H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:45 2009
