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.00034860244
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.0004503446
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
142 LOF: Identifying Density-Based Local Outliers 2000 SIGMOD 0.00029202746
206 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024986675
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
300 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00021810545
478 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017631293
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016121388
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014886692
811 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013745617
826 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.0001363793
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001325914
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013025904
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011774968
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010396565
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010201796
1,589 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010139591
1,634 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001001862
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
1,813 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5801503e-05
1,912 MindReader: Querying databases through multiple examples 1998 VLDB 9.3904326e-05
1,956 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.3169059e-05
1,996 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.216723e-05
2,113 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.0196806e-05
2,263 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.7304715e-05
2,309 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.6626683e-05
2,447 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 8.4499856e-05
2,448 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4494625e-05
2,730 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0861221e-05
2,939 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8340314e-05
3,016 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7483267e-05
3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7330662e-05
3,221 A Raster Approximation for the Processing of Spatial Joins 1998 VLDB 7.5149339e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,302 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4433382e-05
3,377 RINSE: Interactive Data Series Exploration with ADS+ 2015 VLDB 7.357781e-05
3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0277477e-05
3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9458013e-05
4,050 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8298981e-05
4,184 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 6.7540884e-05
4,364 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.6343719e-05
4,728 Finding Near Neighbors Through Cluster Pruning 2007 PODS 6.4473669e-05
4,856 Neighbor-Sensitive Hashing 2016 VLDB 6.3798143e-05
4,972 Computing Clusters of Correlation Connected Objects 2004 SIGMOD 6.3318975e-05
4,986 Indexing for Interactive Exploration of Big Data Series 2014 SIGMOD 6.3264608e-05
5,165 FeedbackBypass: A New Approach to Interactive Similarity Query Processing 2001 VLDB 6.2463919e-05
5,920 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.9475097e-05
5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.93405e-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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0008122792
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045337853
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020019939
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
965 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012809362
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,421 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB
3 1,861 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,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 10,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
8 9,544 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