ACM SIGMOD Anthology VLDB dblp.uni-trier.de

The X-tree : An Index Structure for High-Dimensional Data.

Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39
@inproceedings{DBLP:conf/vldb/BerchtoldKK96,
  author    = {Stefan Berchtold and
               Daniel A. Keim and
               Hans-Peter Kriegel},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {The X-tree : An Index Structure for High-Dimensional Data},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {28-39},
  ee        = {db/conf/vldb/BerchtoldKK96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we propose a new method for indexing large amounts of point and spatial data in high-dimensional space. An analysis shows that index structures such as the R*-tree are not adequate for indexing high-dimensional data sets. The major problem of R-tree-based index structures is the overlap of the bounding boxes in the directory, which increases with growing dimension. To avoid this problem, we introduce a new organization of the directory which uses a split algorithm minimizing overlap and the concept of supernodes. The basic idea of overlap-minimizing split and supernodes is to keep the directory as hierarchical as possible, and at the same time avoiding splits in the directory that would result in high overlap. Our experiments show that for high-dimensional data, the X-tree outperforms the well-known TV-tree and the R*-tree by orders of magnitude.

Copyright © 1996 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

References

[AFS93]
Rakesh Agrawal, Christos Faloutsos, Arun N. Swami: Efficient Similarity Search In Sequence Databases. FODO 1993: 69-84 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AGMM90]
...
[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
[DE82]
G. Dunn, B. Everitt: An Introduction to Mathematical Taxonomy. Cambridge University Press 1982
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fal94]
Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz: Efficient and Effective Querying by Image Content. J. Intell. Inf. Syst. 3(3/4): 231-262(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FL95]
Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174 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
[GN91]
Oliver Günther, Hartmut Noltemeier: Spatial Database Indices for Large Extended Objects. ICDE 1991: 520-526 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Har67]
...
[Jag91]
H. V. Jagadish: A Retrieval Technique for Similar Shapes. SIGMOD Conference 1991: 208-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kuk92]
Karen Kukich: Techniques for Automatically Correcting Words in Text. ACM Comput. Surv. 24(4): 377-439(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KW78]
...
[LJF94]
King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data. VLDB J. 3(4): 517-542(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MG93]
Rajiv Mehrotra, James E. Gary: Feature-Based Retrieval of Similar Shapes. ICDE 1993: 108-115 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MG95]
Rajiv Mehrotra, James E. Gary: Feature-Index-Based Similar Shape Retrieval. VDB 1995: 46-65 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MN95]
...
[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
[RKV95]
Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 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
[SBK92]
...
[SH94]
...
[SK90]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WJ96]
David A. White, Ramesh Jain: Similarity Indexing with the SS-tree. ICDE 1996: 516-523 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WW80]
...

Copyright © Tue Mar 16 02:22:05 2010 by Michael Ley (ley@uni-trier.de)