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
  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,}


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 ... BibTeX

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 BibTeX

Electronic Edition


Rakesh Agrawal, Christos Faloutsos, Arun N. Swami: Efficient Similarity Search In Sequence Databases. FODO 1993: 69-84 BibTeX
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
G. Dunn, B. Everitt: An Introduction to Mathematical Taxonomy. Cambridge University Press 1982
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) BibTeX
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 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Oliver Günther, Hartmut Noltemeier: Spatial Database Indices for Large Extended Objects. ICDE 1991: 520-526 BibTeX
H. V. Jagadish: A Retrieval Technique for Similar Shapes. SIGMOD Conference 1991: 208-217 BibTeX
Karen Kukich: Techniques for Automatically Correcting Words in Text. ACM Comput. Surv. 24(4): 377-439(1992) BibTeX
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) BibTeX
Rajiv Mehrotra, James E. Gary: Feature-Based Retrieval of Similar Shapes. ICDE 1993: 108-115 BibTeX
Rajiv Mehrotra, James E. Gary: Feature-Index-Based Similar Shape Retrieval. VDB 1995: 46-65 BibTeX
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
Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 BibTeX
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
David A. White, Ramesh Jain: Similarity Indexing with the SS-tree. ICDE 1996: 516-523 BibTeX

Referenced by

  1. Stefan Berchtold, Christian Böhm, Daniel A. Keim, Florian Krebs, Hans-Peter Kriegel: On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces. ICDT 2001: 435-449
  2. Edwin M. Knorr, Raymond T. Ng, V. Tucakov: Distance-Based Outliers: Algorithms and Applications. VLDB J. 8(3-4): 237-253(2000)
  3. Kaushik Chakrabarti, Sharad Mehrotra: Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces. VLDB 2000: 89-100
  4. Hyoseop Shin, Bongki Moon, Sukho Lee: Adaptive Multi-Stage Distance Join Processing. SIGMOD Conference 2000: 343-354
  5. Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, Jörg Sander: LOF: Identifying Density-Based Local Outliers. SIGMOD Conference 2000: 93-104
  6. Roger Weber, Klemens Böhm: Trading Quality for Time with Nearest Neighbor Search. EDBT 2000: 21-35
  7. Christian Böhm, Hans-Peter Kriegel: Dynamically Optimizing High-Dimensional Index Structures. EDBT 2000: 36-50
  8. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
  9. Tolga Bozkaya, Z. Meral Özsoyoglu: Indexing Large Metric Spaces for Similarity Search Queries. ACM Trans. Database Syst. 24(3): 361-404(1999)
  10. Joseph K. P. Kuan, Paul H. Lewis: A Study on Data Point Search for HG-Trees. SIGMOD Record 28(1): 90-96(1999)
  11. Ju-Hong Lee, Deok-Hwan Kim, Chin-Wan Chung: Multi-dimensional Selectivity Estimation Using Compressed Histogram Information. SIGMOD Conference 1999: 205-214
  12. Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander: OPTICS: Ordering Points To Identify the Clustering Structure. SIGMOD Conference 1999: 49-60
  13. Kelvin Kam Wing Chu, Man Hon Wong: Fast Time-Series Searching with Scaling and Shifting. PODS 1999: 237-248
  14. Kothuri Venkata Ravi Kanth, Ambuj K. Singh: Optimal Dynamic Range Searching in Non-replicating Index Structures. ICDT 1999: 257-276
  15. Volker Markl, Martin Zirkel, Rudolf Bayer: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm. ICDE 1999: 562-571
  16. Hakan Ferhatosmanoglu, Divyakant Agrawal, Amr El Abbadi: Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching. ICDE 1999: 608-615
  17. Kin-pong Chan, Ada Wai-Chee Fu: Efficient Time Series Matching by Wavelets. ICDE 1999: 126-133
  18. Kaushik Chakrabarti, Sharad Mehrotra: The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. ICDE 1999: 440-447
  19. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
  20. Pavel Zezula, Pasquale Savino, Giuseppe Amato, Fausto Rabitti: Approximate Similarity Retrieval with M-Trees. VLDB J. 7(4): 275-293(1998)
  21. Mihael Ankerst, Hans-Peter Kriegel, Thomas Seidl: A Multistep Approach for Shape Similarity Search in Image Databases. IEEE Trans. Knowl. Data Eng. 10(6): 996-1004(1998)
  22. King Lum Cheung, Ada Wai-Chee Fu: Enhanced Nearest Neighbour Search on the R-tree. SIGMOD Record 27(3): 16-21(1998)
  23. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  24. Geraldo Zimbrao, Jano Moreira de Souza: A Raster Approximation For Processing of Spatial Joins. VLDB 1998: 558-569
  25. Roger Weber, Hans-Jörg Schek, Stephen Blott: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB 1998: 194-205
  26. Erik Riedel, Garth A. Gibson, Christos Faloutsos: Active Storage for Large-Scale Data Mining and Multimedia. VLDB 1998: 62-73
  27. Beng Chin Ooi, Cheng Hian Goh, Kian-Lee Tan: Fast High-Dimensional Data Search in Incomplete Databases. VLDB 1998: 357-367
  28. Yoshiharu Ishikawa, Ravishankar Subramanya, Christos Faloutsos: MindReader: Querying Databases Through Multiple Examples. VLDB 1998: 218-227
  29. Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl: Improving Adaptable Similarity Query Processing by Using Approximations. VLDB 1998: 206-217
  30. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
  31. Thomas Seidl, Hans-Peter Kriegel: Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD Conference 1998: 154-165
  32. Apostolos Papadopoulos, Yannis Manolopoulos: Similarity Query Processing Using Disk Arrays. SIGMOD Conference 1998: 225-236
  33. Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh: Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998: 166-176
  34. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: The Pyramid-Technique: Towards Breaking the Curse of Dimensionality. SIGMOD Conference 1998: 142-153
  35. Sibel Adali, Piero A. Bonatti, Maria Luisa Sapino, V. S. Subrahmanian: A Multi-Similarity Algebra. SIGMOD Conference 1998: 402-413
  36. Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178
  37. Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis: Cost Models for Join Queries in Spatial Databases. ICDE 1998: 476-483
  38. Nick Koudas, Kenneth C. Sevcik: High Dimensional Similarity Joins: Algorithms and Performance Evaluation. ICDE 1998: 466-475
  39. Andreas Henrich: The LSDh-Tree: An Access Structure for Feature Vectors. ICDE 1998: 362-369
  40. Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft: Compressing Relations and Indexes. ICDE 1998: 370-379
  41. Stefan Berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, Thomas Seidl: Fast Nearest Neighbor Search in High-Dimensional Space. ICDE 1998: 209-218
  42. Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel: Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations. EDBT 1998: 216-230
  43. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
  44. Thomas Seidl, Hans-Peter Kriegel: Efficient User-Adaptable Similarity Search in Large Multimedia Databases. VLDB 1997: 506-515
  45. Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435
  46. Norio Katayama, Shin'ichi Satoh: The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. SIGMOD Conference 1997: 369-380
  47. Stefan Berchtold, Hans-Peter Kriegel: S3: Similarity Search in CAD Database Systems. SIGMOD Conference 1997: 564-567
  48. Stefan Berchtold, Christian Böhm, Bernhard Braunmüller, Daniel A. Keim, Hans-Peter Kriegel: Fast Parallel Similarity Search in Multimedia Databases. SIGMOD Conference 1997: 1-12
  49. Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel: A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space. PODS 1997: 78-86
  50. Heikki Mannila: Methods and Problems in Data Mining. ICDT 1997: 41-55
  51. Kyuseok Shim, Ramakrishnan Srikant, Rakesh Agrawal: High-Dimensional Similarity Joins. ICDE 1997: 301-311
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:09 2009