What is the nearest neighbor in high dimensional spaces?

Summary: Redefines high-dimensional NN as a generalized problem by choosing query-specific projections. Projections are scored by how well data clusters around the query, enabling an efficient algorithm and revealing new insights into high-dimensional NN behavior. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8866
Venue: VLDB
Year: 2000
Pagerank: 9.0622995e-05
Overall Rank: 2,158 | 85.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alexander Hinneburg (University of Halle)
2. Charu C. Aggarwal (IBM)
3. Daniel A. Keim (University of Halle)

BibTeX Citation

@article{hinneburg_vldb00,
        title = {{What is the nearest neighbor in high dimensional spaces?}},
        author = {Hinneburg, Alexander and Aggarwal, Charu C. and Keim, Daniel A.},
        journal = {PVLDB},
        series = {{VLDB} '00},
        pages = {506},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,572	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010329197
3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.5711218e-05
3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	7.4808966e-05
3,550	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.3200789e-05
4,209	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.8319192e-05
5,800	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0850924e-05
6,483	Similarity Search: A Matching Based Approach	2006	VLDB	5.8667204e-05
6,646	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.8148791e-05
7,145	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.6908957e-05
9,914	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations	2025	PODS	5.1955087e-05
10,297	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	5.093636e-05
12,602	Detecting Clusters in Moderate-to-High Dimensional Data: Subspace Clustering, Pattern-based Clustering, and Correlation Clustering	2008	VLDB	5.093636e-05
12,647	AutoDomainMine: A Graphical Data Mining System for Process Optimization	2007	SIGMOD	5.093636e-05
12,764	k-Means Projective Clustering	2004	PODS	5.093636e-05
12,863	Fast Evaluation Techniques for Complex Similarity Queries	2001	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.0020210012
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761
1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00010128564
1,776	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	9.7853414e-05
1,833	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.6566846e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,282	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB
2	1,833	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD
3	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
4	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
5	13,768	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB
6	580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
7	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
8	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
9	581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
10	1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS