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
8330
Venue
VLDB
Year
1996
Pagerank
0.00044255276
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,173 Similarity Search: A Matching Based Approach 2006 VLDB 5.1684255e-05
6,249 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 5.132996e-05
6,316 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1098143e-05
6,359 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.0912204e-05
6,436 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.0554554e-05
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
7,198 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 4.79852e-05
7,539 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7116182e-05
7,583 Scaling and Time Warping in Time Series Querying 2005 VLDB 4.7016397e-05
7,635 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 4.6864934e-05
8,127 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5757206e-05
8,128 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 4.5757206e-05
8,471 Adaptive Index Structures 2002 VLDB 4.4986491e-05
8,559 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4893996e-05
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.423024e-05
9,092 Challenges and Techniques for Effective and Efficient Similarity Search in Large Video Databases 2008 VLDB 4.3934714e-05
9,120 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 4.3881453e-05
9,173 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3807204e-05
9,209 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 4.3691119e-05
9,261 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 4.3648789e-05
9,532 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 4.3232695e-05
9,852 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 4.2671421e-05
10,062 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 4.1905499e-05
10,326 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.1905499e-05
11,110 Counterfactual Explanation Analytics: Empowering Lay Users to Take Action Against Consequential Automated Decisions 2024 VLDB 4.1905499e-05
11,777 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.1905499e-05
12,099 QuEval: Beyond high-dimensional indexing a la carte 2013 VLDB 4.1905499e-05
12,143 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.1905499e-05
12,285 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1905499e-05
12,475 IndeGS: Index Supported Graphics Data Server for CFD Data Postprocessing 2007 VLDB 4.1905499e-05
12,530 Indexing for Function Approximation 2006 VLDB 4.1905499e-05
12,610 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1905499e-05
12,634 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1905499e-05
12,739 A Multi-Similarity Algebra 1998 SIGMOD 4.1905499e-05
12,756 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1905499e-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.0032118946
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018380955
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032141918
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022348285
833 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016085787
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,592 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 8.4841264e-05
2,558 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5441554e-05
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
9,769 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2815042e-05
9,209 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 4.3691119e-05
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888