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: 3456
Venue: SIGMOD
Year: 2003
Pagerank: 4.4937074e-05
Overall Rank: 8,562 | 40.44%
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,521	Indexing for Function Approximation	2006	VLDB	4.1945683e-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
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
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
531	Improving Index Performance through Prefetching	2001	SIGMOD	0.00020790058
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
1,806	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010490769
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
1,983	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.8638201e-05
3,300	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2516103e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,387	Parallel kd-tree with Batch Updates	2025	SIGMOD	4.1945683e-05
7,239	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	4.792836e-05
8,647	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	4.4768766e-05
1,183	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455596
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
3,225	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	7.3463484e-05
3,061	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6382127e-05
3,300	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2516103e-05
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858