DBScholar

Back to papers

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

Summary: Proposes the X-tree, a high-dimensional index for point and spatial data. Replaces R*-tree-style splits with overlap-minimizing splits and supernodes to keep a hierarchical directory and minimize bounding-box overlap; reports up to 100x speedups over R*-tree and TV-tree on high-D data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h3f62ba6d592ff680
Venue
VLDB
Year
1996
Pagerank
0.00034847854
Overall Rank
90 | 99.40%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{berchtold_vldb96,
        title = {{The X-tree: An Index Structure for High-Dimensional Data}},
        author = {Berchtold, Stefan and Keim, Daniel A. and Kriegel, Hans-Peter},
        journal = {PVLDB},
        series = {{VLDB} '96},
        pages = {28--39},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 87 citing papers.

Rank Citing Paper Year Venue Pagerank
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00045027197
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040363819
142 LOF: Identifying Density-Based Local Outliers 2000 SIGMOD 0.00029189529
207 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024976482
281 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022303081
300 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00021800242
479 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017623894
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016118297
648 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015156941
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014886449
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013744009
826 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.000136317
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013253709
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013028642
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.0001176973
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.0001039208
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010197322
1,590 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010134811
1,634 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010013999
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6212318e-05
1,814 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5757565e-05
1,913 MindReader: Querying databases through multiple examples 1998 VLDB 9.386654e-05
1,957 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.3126922e-05
1,998 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.2123795e-05
2,114 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.0164212e-05
2,265 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.7267108e-05
2,312 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.658611e-05
2,444 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4556406e-05
2,449 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 8.4460399e-05
2,730 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0842027e-05
2,940 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8306095e-05
3,017 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7455245e-05
3,035 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7296096e-05
3,223 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 7.5114215e-05
3,254 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.487573e-05
3,304 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4398851e-05
3,377 RINSE: Interactive Data Series Exploration with ADS+ 2015 VLDB 7.354298e-05
3,776 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0244572e-05
3,886 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9430152e-05
4,051 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8266649e-05
4,184 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 6.7508911e-05
4,367 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.6312601e-05
4,730 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4444432e-05
4,852 Neighbor-Sensitive Hashing 2016 VLDB 6.3776281e-05
4,974 Computing Clusters of Correlation Connected Objects 2004 SIGMOD 6.3289112e-05
4,989 Indexing for Interactive Exploration of Big Data Series 2014 SIGMOD 6.3234684e-05
5,167 FeedbackBypass: A New Approach to Interactive Similarity Query Processing 2001 VLDB 6.2434494e-05
5,903 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.9512758e-05
5,958 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.931243e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081200096
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045319457
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020011298
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017451091
967 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012803465
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,828 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
2 2,422 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB
3 1,862 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
4 4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD
5 1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB
6 3,035 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 10,053 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
8 9,554 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR
9 2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD
10 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB