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

Rank Citing Paper Year Venue Pagerank
6,140 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 5.8734337e-05
6,181 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.8595125e-05
6,203 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.8507344e-05
6,232 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.84313e-05
6,540 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7523628e-05
6,610 Similarity Search: A Matching Based Approach 2006 VLDB 5.7350971e-05
6,740 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6916981e-05
7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5598057e-05
7,494 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.5095043e-05
7,541 Scaling and Time Warping in Time Series Querying 2005 VLDB 5.4988401e-05
8,377 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 5.3435192e-05
8,566 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.3137327e-05
8,567 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 5.3137327e-05
8,818 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2700772e-05
8,856 Adaptive Index Structures 2002 VLDB 5.2635701e-05
8,927 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.2559789e-05
9,204 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.2080128e-05
9,412 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 5.1826275e-05
9,436 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 5.1780501e-05
9,544 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.1611019e-05
9,582 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 5.1571823e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-05
9,833 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.1243105e-05
10,204 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.0605896e-05
10,555 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.9793485e-05
11,059 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.9793485e-05
11,631 Counterfactual Explanation Analytics: Empowering Lay Users to Take Action Against Consequential Automated Decisions 2024 VLDB 4.9793485e-05
12,272 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.9793485e-05
12,579 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 4.9793485e-05
12,622 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.9793485e-05
12,763 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.9793485e-05
12,950 IndeGS: Index Supported Graphics Data Server for CFD Data Postprocessing 2007 VLDB 4.9793485e-05
13,004 Indexing for Function Approximation 2006 VLDB 4.9793485e-05
13,084 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9793485e-05
13,108 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.9793485e-05
13,213 A Multi-Similarity Algebra 1998 SIGMOD 4.9793485e-05
13,230 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.9793485e-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.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