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.0164212e-05
Overall Rank: 2,114 | 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,527	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010350688
2,955	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.8111585e-05
3,322	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	7.4261592e-05
3,618	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.1525532e-05
4,301	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.6757672e-05
5,530	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0907372e-05
6,614	Similarity Search: A Matching Based Approach	2006	VLDB	5.7323821e-05
6,744	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.6891153e-05
7,267	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5677188e-05
10,105	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations	2025	PODS	5.0765311e-05
10,520	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	4.9769913e-05
10,837	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB	4.9769913e-05
12,898	Detecting Clusters in Moderate-to-High Dimensional Data: Subspace Clustering, Pattern-based Clustering, and Correlation Clustering	2008	VLDB	4.9769913e-05
12,943	AutoDomainMine: A Graphical Data Mining System for Process Optimization	2007	SIGMOD	4.9769913e-05
13,060	k-Means Projective Clustering	2004	PODS	4.9769913e-05
13,159	Fast Evaluation Techniques for Complex Similarity Queries	2001	VLDB	4.9769913e-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.0019923528
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00045027197
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034847854
839	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.0001354488
1,679	Fast Algorithms for Projected Clustering	1999	SIGMOD	9.90334e-05
1,814	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	9.5757565e-05
1,882	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.4359061e-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,882	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,338	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
5	14,084	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