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: 8675
Venue: VLDB
Year: 2000
Pagerank: 9.5330494e-05
Overall Rank: 2,107 | 85.35%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,971	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.893198e-05
3,376	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.1630476e-05
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
4,552	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.0922282e-05
6,164	Similarity Search: A Matching Based Approach	2006	VLDB	5.1733919e-05
6,325	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.1105081e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
7,843	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6367909e-05
9,761	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations	2025	PODS	4.2856106e-05
12,408	Detecting Clusters in Moderate-to-High Dimensional Data: Subspace Clustering, Pattern-based Clustering, and Correlation Clustering	2008	VLDB	4.1945683e-05
12,453	AutoDomainMine: A Graphical Data Mining System for Process Optimization	2007	SIGMOD	4.1945683e-05
12,571	k-Means Projective Clustering	2004	PODS	4.1945683e-05
12,670	Fast Evaluation Techniques for Complex Similarity Queries	2001	VLDB	4.1945683e-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.0032169493
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018451109
1,595	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011222442
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010669106
2,019	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.7707059e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,061	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6382127e-05
2,019	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.7707059e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
9,025	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4072367e-05
13,568	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB	-
867	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015792021
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
709	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017768547
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
1,183	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455596