A General Solution of the n-dimensional B-tree Problem.
Michael Freeston:
A General Solution of the n-dimensional B-tree Problem.
SIGMOD Conference 1995: 80-91@inproceedings{DBLP:conf/sigmod/Freeston95,
author = {Michael Freeston},
editor = {Michael J. Carey and
Donovan A. Schneider},
title = {A General Solution of the n-dimensional B-tree Problem},
booktitle = {Proceedings of the 1995 ACM SIGMOD International Conference on
Management of Data, San Jose, California, May 22-25, 1995},
publisher = {ACM Press},
year = {1995},
pages = {80-91},
ee = {http://doi.acm.org/10.1145/223784.223796, db/conf/sigmod/Freeston95.html},
crossref = {DBLP:conf/sigmod/95},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
We present a generic solution to a problem which lies at the heart of the
unpredictable worst-case performance characteristics of a wide class of
multi-dimensional index designs: those which employ a recursive partitioning
of the data space. We then show how this solution can produce modified designs
with fully predictable and controllable worst-case characteristics.
In particular, we show how the recursive partitioning of an n-dimensional
dataspace can be represented in such a way that the characteristics of the
one-dimensional B-tree are preserved in n dimensions, as far as is topologically
possible i.e. a representation guaranteeing logarithmic access and update time,
while also guaranteeing a one-third minimum occupancy of both data and index nodes.
Copyright © 1995 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Michael J. Carey, Donovan A. Schneider (Eds.):
Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995.
ACM Press 1995 BibTeX
,
SIGMOD Record 24(2),
June 1995
Contents
[Index Terms]
[Full Text in PDF Format, 1408 KB]
References
- [Ben75]
- Jon Louis Bentley:
Multidimensional Binary Search Trees Used for Associative Searching.
Commun. ACM 18(9): 509-517(1975) BibTeX
- [Ben79]
- Jon Louis Bentley:
Multidimensional Binary Search Trees in Database Applications.
IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
- [BM72]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indices.
Acta Inf. 1: 173-189(1972) BibTeX
- [BU77]
- Rudolf Bayer, Karl Unterauer:
Prefix B-Trees.
ACM Trans. Database Syst. 2(1): 11-26(1977) BibTeX
- [Com79]
- Douglas Comer:
The Ubiquitous B-Tree.
ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
- [Fre87]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269 BibTeX
- [Fre89a]
- Michael Freeston:
Advances in the Design of the BANG File.
FODO 1989: 322-338 BibTeX
- [Fre89b]
- Michael Freeston:
A Well-Behaved File Structure for the Storage of Spatial Objects.
SSD 1989: 287-300 BibTeX
- [Fre94]
- ...
- [Gut84]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [HSW89]
- Andreas Henrich, Hans-Werner Six, Peter Widmayer:
The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects.
VLDB 1989: 45-53 BibTeX
- [KSS+90]
- Hans-Peter Kriegel, Michael Schiwietz:
Performance Comparison of Point and Spatial Access Methods.
SSD 1989: 89-114 BibTeX
- [LS89]
- David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
- [Ore86]
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336 BibTeX
- [Rob81]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18 BibTeX
- [Sam89]
- Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
BibTeX
- [SK90]
- Bernhard Seeger, Hans-Peter Kriegel:
The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems.
VLDB 1990: 590-601 BibTeX
- [SRF87]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518 BibTeX
Referenced by
- Kothuri Venkata Ravi Kanth, Ambuj K. Singh:
Optimal Dynamic Range Searching in Non-replicating Index Structures.
ICDT 1999: 257-276
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh:
Dimensionality Reduction for Similarity Searching in Dynamic Databases.
SIGMOD Conference 1998: 166-176
- Ming-Chuan Wu, Alejandro P. Buchmann:
Encoded Bitmap Indexing for Data Warehouses.
ICDE 1998: 220-230
- Thomas A. Mück, Martin L. Polaschek:
A Configrable Type Hierarchy Index for OODB.
VLDB J. 6(4): 312-332(1997)
- Thomas A. Mück, Martin L. Polaschek:
The Multikey Type Index for Persistent Object Sets.
ICDE 1997: 22-31
- Thomas A. Mück, Martin L. Polaschek:
Optimal Type Hierarchy Linearization for Queries in OODB.
DASFAA 1997: 225-234
- Nick Koudas, Christos Faloutsos, Ibrahim Kamel:
Declustering Spatial Databases on a Multi-Computer Architecture.
EDBT 1996: 592-614
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
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:40:25 2009
