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: hbbc55fca2bc7a09d
Venue: VLDB
Year: 2000
Pagerank: 9.0196806e-05
Overall Rank: 2,113 | 85.80%
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 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,530	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010344205
2,969	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.8000797e-05
3,325	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	7.4271038e-05
3,618	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.1559402e-05
4,299	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.6789252e-05
5,527	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0936219e-05
6,610	Similarity Search: A Matching Based Approach	2006	VLDB	5.7350971e-05
6,740	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.6916981e-05
7,264	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5703557e-05
10,101	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations	2025	PODS	5.0789354e-05
10,509	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	4.9793485e-05
10,827	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB	4.9793485e-05
12,892	Detecting Clusters in Moderate-to-High Dimensional Data: Subspace Clustering, Pattern-based Clustering, and Correlation Clustering	2008	VLDB	4.9793485e-05
12,937	AutoDomainMine: A Graphical Data Mining System for Process Optimization	2007	SIGMOD	4.9793485e-05
13,054	k-Means Projective Clustering	2004	PODS	4.9793485e-05
13,153	Fast Evaluation Techniques for Complex Similarity Queries	2001	VLDB	4.9793485e-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.001992968
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
837	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013551047
1,679	Fast Algorithms for Projected Clustering	1999	SIGMOD	9.9079414e-05
1,813	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	9.5801503e-05
1,881	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.4403736e-05

Semantically Similar Papers

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