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: hb1986415b7c5d600
Venue: SIGMOD
Year: 2003
Pagerank: 5.2559789e-05
Overall Rank: 8,927 | 39.99%
DOI: 10.1145/872757.872815

Incoming Non-self Citations Over Time

Authors

1. Bin Cui (National University of Singapore)
2. Beng Chin Ooi (National University of Singapore)
3. Jianwen Su (University of California Santa Barbara)
4. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@inproceedings{cui_sigmod03,
        title = {{Contorting High Dimensional Data for Efficient Main Memory KNN Processing}},
        author = {Cui, Bin and Ooi, Beng Chin and Su, Jianwen and Tan, Kian-Lee},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872815},
        url = {https://dl.acm.org/doi/10.1145/872757.872815},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,004	Indexing for Function Approximation	2006	VLDB	4.9793485e-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
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
69	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037950385
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
548	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016569534
597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00015766567
1,634	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001001862
1,841	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5268075e-05
2,016	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.1771614e-05
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,115	Parallel kd-tree with Batch Updates	2025	SIGMOD
2	6,239	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB
3	8,818	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
4	1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
5	12,054	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
6	3,325	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
7	3,320	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB
8	2,448	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB
9	3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB
10	650	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB