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 37 of 87 citing papers.

Rank Citing Paper Year Venue Pagerank
6,079 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.9850223e-05
6,093 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.978635e-05
6,149 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.9581422e-05
6,404 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.8859287e-05
6,426 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.8809448e-05
6,483 Similarity Search: A Matching Based Approach 2006 VLDB 5.8667204e-05
6,646 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.8148791e-05
7,151 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.6873519e-05
7,350 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.6358517e-05
7,402 Scaling and Time Warping in Time Series Querying 2005 VLDB 5.6250511e-05
8,210 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 5.4661361e-05
8,391 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.4356884e-05
8,392 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 5.4356884e-05
8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.3910353e-05
8,689 Adaptive Index Structures 2002 VLDB 5.3843737e-05
8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.3766157e-05
9,034 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.3274671e-05
9,238 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 5.3015807e-05
9,262 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 5.2968259e-05
9,365 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.279561e-05
9,400 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 5.2755515e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
9,657 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.2419252e-05
10,015 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.17669e-05
10,354 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 5.093636e-05
10,612 Index Intersection for High-Dimensional Range Queries 2026 VLDB 5.093636e-05
11,313 Counterfactual Explanation Analytics: Empowering Lay Users to Take Action Against Consequential Automated Decisions 2024 VLDB 5.093636e-05
11,974 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 5.093636e-05
12,288 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 5.093636e-05
12,331 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 5.093636e-05
12,472 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 5.093636e-05
12,660 IndeGS: Index Supported Graphics Data Server for CFD Data Postprocessing 2007 VLDB 5.093636e-05
12,714 Indexing for Function Approximation 2006 VLDB 5.093636e-05
12,794 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 5.093636e-05
12,818 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 5.093636e-05
12,923 A Multi-Similarity Algebra 1998 SIGMOD 5.093636e-05
12,940 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 5.093636e-05
Previous Page 2 / 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