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}
}
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 ...
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
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
- [BM72]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indices.
Acta Inf. 1: 173-189(1972)
- [Bur83]
- Walter A. Burkhard:
Interpolation-Based Index Maintenance.
BIT 23(3): 274-294(1983)
- [FSR87]
- Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos:
Analysis of Object Oriented Spatial Access Methods.
SIGMOD Conference 1987: 426-439
- [Fre87]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- [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
- [Hin85]
- ...
- [HSW88]
- Andreas Hutflesz, Hans-Werner Six, Peter Widmayer:
Twin Grid Files: Space Optimizing Access Schemes.
SIGMOD Conference 1988: 183-190
- [Kri84]
- Hans-Peter Kriegel:
Performance Comparison of Index Structures for Multi-Key Retrieval.
SIGMOD Conference 1984: 186-196
- [KS86]
- Hans-Peter Kriegel, Bernhard Seeger:
Multidimensional Order Preserving Linear Hashing with Partial Expansions.
ICDT 1986: 203-220
- [KS88]
- Hans-Peter Kriegel, Bernhard Seeger:
PLOP-Hashing: A Grid File without Directory.
ICDE 1988: 369-376
- [KS89]
- ...
- [KSSS89]
- Hans-Peter Kriegel, Michael Schiwietz:
Performance Comparison of Point and Spatial Access Methods.
SSD 1989: 89-114
- [LS89]
- David B. Lomet, Betty Salzberg:
A Robust Multi-Attribute Search Structure.
ICDE 1989: 296-304
- [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)
- [Ore82]
- Jack A. Orenstein:
Multidimensional Tries Used for Associative Searching.
Inf. Process. Lett. 14(4): 150-157(1982)
- [OM84]
- Jack A. Orenstein, T. H. Merrett:
A Class of Data Structures for Associative Searching.
PODS 1984: 181-190
- [Oto84]
- Ekow J. Otoo:
A Mapping Function for the Directory of a Multidimensional Extendible Hashing.
VLDB 1984: 493-506
- [Oto86]
- Ekow J. Otoo:
Balanced Multidimensional Extendible Hash Tree.
PODS 1986: 100-113
- [Ouk85]
- Aris M. Ouksel:
The Interpolation-Based Grid File.
PODS 1985: 20-27
- [Rob81]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18
- [See89]
- ...
- [SK88]
- Bernhard Seeger, Hans-Peter Kriegel:
Techniques for Design and Implementation of Efficient Spatial Access Methods.
VLDB 1988: 360-371
- [Tam82]
- Markku Tamminen:
The Extendible Cell Method for Closest Point Problems.
BIT 22(1): 27-41(1982)
- [WK85]
- ...
Copyright © Tue Mar 16 02:22:01 2010
by Michael Ley (ley@uni-trier.de)
