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

Rank	Citing Paper	Year	Venue	Pagerank
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
161	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00039846974
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031110894
270	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029505642
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
539	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020666392
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
802	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016502317
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517
931	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00015238406
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
1,183	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455596
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856
1,608	MindReader: Querying databases through multiple examples	1998	VLDB	0.00011151257
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010669106
1,806	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010490769
1,925	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010073407
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
2,089	Active Storage For Large-Scale Data Mining and Multimedia	1998	VLDB	9.5657612e-05
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,147	RINSE: Interactive Data Series Exploration with ADS+	2015	VLDB	9.4325176e-05
2,281	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1077704e-05
2,516	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6106981e-05
2,534	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.5890923e-05
2,703	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	8.2722965e-05
3,018	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.7002798e-05
3,183	Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search	2020	VLDB	7.4228241e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
3,275	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2897998e-05
3,300	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2516103e-05
3,338	Fast Time-Series Searching with Scaling and Shifting	1999	PODS	7.2040692e-05
3,555	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9772546e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
4,090	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4577834e-05
4,162	Computing Clusters of Correlation Connected Objects	2004	SIGMOD	6.3937203e-05
4,755	Indexing for Interactive Exploration of Big Data Series	2014	SIGMOD	5.946863e-05
4,823	YADING: Fast Clustering of Large-Scale Time Series Data	2015	VLDB	5.8956566e-05
5,224	Neighbor-Sensitive Hashing	2016	VLDB	5.6197981e-05
5,328	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5665496e-05
5,344	FeedbackBypass: A New Approach to Interactive Similarity Query Processing	2001	VLDB	5.5576339e-05
5,569	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.4290942e-05
5,882	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2892937e-05
5,997	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.2415551e-05

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

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