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: 3518
Venue: SIGMOD
Year: 2003
Pagerank: 5.3766157e-05
Overall Rank: 8,765 | 39.87%
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
12,714	Indexing for Function Approximation	2006	VLDB	5.093636e-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
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
545	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016766463
592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00016029789
1,602	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010239526
1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.6941032e-05
1,978	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.3627341e-05
2,979	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.8984588e-05

Semantically Similar Papers

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