Database Paper Browser

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
8329
Venue
VLDB
Year
1996
Pagerank
0.0004429571
Overall Rank
129 | 99.11%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 37 of 87 citing papers.

Rank Citing Paper Year Venue Pagerank
6,164 Similarity Search: A Matching Based Approach 2006 VLDB 5.1733919e-05
6,243 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 5.1402191e-05
6,325 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1105081e-05
6,360 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.0961051e-05
6,441 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.0603113e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
7,054 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8496866e-05
7,204 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 4.8015761e-05
7,540 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7159549e-05
7,578 Scaling and Time Warping in Time Series Querying 2005 VLDB 4.7061534e-05
7,636 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 4.6907372e-05
8,123 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5801104e-05
8,124 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 4.5801104e-05
8,474 Adaptive Index Structures 2002 VLDB 4.5029015e-05
8,562 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4937074e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.427268e-05
9,096 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 4.3974472e-05
9,122 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 4.3922853e-05
9,143 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3850454e-05
9,207 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 4.3733038e-05
9,254 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 4.3690661e-05
9,531 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 4.3274164e-05
9,853 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 4.2711871e-05
10,062 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.1945683e-05
10,314 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.1945683e-05
11,107 Counterfactual Explanation Analytics: Empowering Lay Users to Take Action Against Consequential Automated Decisions 2024 VLDB 4.1945683e-05
11,769 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.1945683e-05
12,091 QuEval: Beyond high-dimensional indexing a la carte 2013 VLDB 4.1945683e-05
12,135 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.1945683e-05
12,277 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1945683e-05
12,466 IndeGS: Index Supported Graphics Data Server for CFD Data Postprocessing 2007 VLDB 4.1945683e-05
12,521 Indexing for Function Approximation 2006 VLDB 4.1945683e-05
12,601 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1945683e-05
12,625 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1945683e-05
12,730 A Multi-Similarity Algebra 1998 SIGMOD 4.1945683e-05
12,747 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1945683e-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.0032169493
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018397217
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032163466
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022364776
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,586 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 8.4928908e-05
2,541 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5795657e-05
2,030 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7378136e-05
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
3,255 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3160522e-05
9,767 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2856106e-05
9,207 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 4.3733038e-05
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538