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

Rank	Citing Paper	Year	Venue	Pagerank
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
159	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00040135453
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031093647
263	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029955858
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
537	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020650291
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
798	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00016484637
821	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016232579
929	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001523035
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,180	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455619
1,225	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013182109
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
1,568	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.0001131667
1,613	MindReader: Querying databases through multiple examples	1998	VLDB	0.00011141103
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010661725
1,802	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001048177
1,923	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	0.00010079134
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
2,093	Active Storage For Large-Scale Data Mining and Multimedia	1998	VLDB	9.5570993e-05
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
2,151	RINSE: Interactive Data Series Exploration with ADS+	2015	VLDB	9.4234044e-05
2,285	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1097273e-05
2,519	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6048934e-05
2,532	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.5886308e-05
2,708	A Raster Approximation for the Processing of Spatial Joins	1998	VLDB	8.2643522e-05
3,018	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.6995792e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,199	Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search	2020	VLDB	7.3999833e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
3,278	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2858181e-05
3,301	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2450912e-05
3,340	Fast Time-Series Searching with Scaling and Shifting	1999	PODS	7.1987694e-05
3,549	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD	6.9792126e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
4,096	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4506806e-05
4,125	Computing Clusters of Correlation Connected Objects	2004	SIGMOD	6.4248096e-05
4,751	Indexing for Interactive Exploration of Big Data Series	2014	SIGMOD	5.9411478e-05
4,792	YADING: Fast Clustering of Large-Scale Time Series Data	2015	VLDB	5.9132429e-05
5,218	Neighbor-Sensitive Hashing	2016	VLDB	5.6204105e-05
5,294	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB	5.5777973e-05
5,354	FeedbackBypass: A New Approach to Interactive Similarity Query Processing	2001	VLDB	5.5526135e-05
5,577	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.423881e-05
5,889	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2842168e-05
6,001	FACET: Robust Counterfactual Explanation Analytics	2023	SIGMOD	5.2365238e-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.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

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