Contorting High Dimensional Data for Efficient Main Memory KNN Processing

Summary: Delta-tree is a multi-level main-memory index for high-dimensional KNN, where leaves store full dimensions and upper levels use PCA-projected spaces to prune search and speed distance computations. Delta+-tree adds clustering with regional partitioning; experiments show superior performance across diverse datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3457
Venue: SIGMOD
Year: 2003
Pagerank: 4.4893996e-05
Overall Rank: 8,559 | 40.52%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,530	Indexing for Function Approximation	2006	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited 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
104	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049475932
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
622	Improving Index Performance through Prefetching	2001	SIGMOD	0.00018976783
1,802	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001048177
1,807	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.0001047644
1,987	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.8561164e-05
3,301	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2450912e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,398	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.1905499e-05
7,235	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.7882389e-05
8,645	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4725847e-05
1,180	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455619
11,558	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1905499e-05
3,574	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9520978e-05
3,182	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.4280768e-05
3,062	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6348035e-05
3,301	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2450912e-05
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051