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.00034749222
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.00044967652
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0004024707
143 LOF: Identifying Density-Based Local Outliers 2000 SIGMOD 0.00029095978
210 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024910589
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
300 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00021743411
481 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017567157
578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016079505
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014872783
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013710393
828 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013588099
889 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013212387
925 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013026835
1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012114187
1,161 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011733128
1,520 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010358287
1,574 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010164216
1,594 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010103178
1,642 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 9.9812004e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,825 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5443954e-05
1,921 MindReader: Querying databases through multiple examples 1998 VLDB 9.3580039e-05
1,965 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.2829035e-05
2,007 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.182637e-05
2,129 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 8.9877592e-05
2,279 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.6989205e-05
2,322 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.6301008e-05
2,426 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4692316e-05
2,456 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 8.4204678e-05
2,733 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0653682e-05
2,952 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8061763e-05
3,025 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7214661e-05
3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7045269e-05
3,232 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 7.4890975e-05
3,267 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.46539e-05
3,315 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4155055e-05
3,388 RINSE: Interactive Data Series Exploration with ADS+ 2015 VLDB 7.3299881e-05
3,784 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0012942e-05
3,893 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9232481e-05
4,077 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8040917e-05
4,201 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 6.7286195e-05
4,391 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.6093384e-05
4,749 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.423839e-05
4,873 Neighbor-Sensitive Hashing 2016 VLDB 6.3580715e-05
5,000 Computing Clusters of Correlation Connected Objects 2004 SIGMOD 6.3080199e-05
5,013 Indexing for Interactive Exploration of Big Data Series 2014 SIGMOD 6.30259e-05
5,188 FeedbackBypass: A New Approach to Interactive Similarity Query Processing 2001 VLDB 6.2228139e-05
5,891 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.9396547e-05
5,970 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.9116326e-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.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
361 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00019948113
490 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017397036
968 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012763144
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,818 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
2 2,436 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB
3 1,869 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,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB
6 3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
8 9,579 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