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
8520
Venue
VLDB
Year
1996
Pagerank
0.00035405879
Overall Rank
85 | 99.42%
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
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
142 LOF: Identifying Density-Based Local Outliers 2000 SIGMOD 0.0002962566
202 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00025454884
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
291 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00022264197
468 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017986163
581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016153395
690 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.0001492934
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
796 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013932561
797 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013927251
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00012796562
1,053 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012401532
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,486 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010625076
1,561 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010361147
1,602 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010239526
1,612 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010218134
1,776 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.7853414e-05
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,862 MindReader: Querying databases through multiple examples 1998 VLDB 9.5951515e-05
1,901 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.5068846e-05
1,993 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.3421788e-05
2,158 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.0622995e-05
2,227 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.9111106e-05
2,254 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.8603695e-05
2,426 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 8.5987569e-05
2,572 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4027322e-05
2,734 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.190416e-05
2,886 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.9957585e-05
2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.9083221e-05
2,979 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.8984588e-05
3,170 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 7.6703896e-05
3,217 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.6314544e-05
3,252 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.5951443e-05
3,322 RINSE: Interactive Data Series Exploration with ADS+ 2015 VLDB 7.5213802e-05
3,710 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.1780127e-05
3,866 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 7.061829e-05
4,151 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 6.8703273e-05
4,657 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.5830079e-05
4,712 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.5506649e-05
4,856 Computing Clusters of Correlation Connected Objects 2004 SIGMOD 6.4752952e-05
4,883 Indexing for Interactive Exploration of Big Data Series 2014 SIGMOD 6.4648124e-05
4,927 Neighbor-Sensitive Hashing 2016 VLDB 6.4426453e-05
5,042 FeedbackBypass: A New Approach to Interactive Similarity Query Processing 2001 VLDB 6.3896532e-05
5,304 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.2733516e-05
5,838 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 6.0702428e-05
6,016 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 6.0082425e-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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
350 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020425134
483 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017756569
936 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00013092484
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,776 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
2 2,375 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB
3 1,814 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,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB
6 2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
8 9,365 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 42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB