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: 8676
Venue: VLDB
Year: 2000
Pagerank: 9.5429949e-05
Overall Rank: 2,099 | 85.42%
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,966	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	9.9130791e-05
3,381	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.1538392e-05
3,574	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9520978e-05
4,230	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.3337893e-05
4,549	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.0866685e-05
6,173	Similarity Search: A Matching Based Approach	2006	VLDB	5.1684255e-05
6,316	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.1098143e-05
6,375	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0868008e-05
7,848	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6323445e-05
9,763	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations	2025	PODS	4.2815042e-05
12,417	Detecting Clusters in Moderate-to-High Dimensional Data: Subspace Clustering, Pattern-based Clustering, and Correlation Clustering	2008	VLDB	4.1905499e-05
12,462	AutoDomainMine: A Graphical Data Mining System for Process Optimization	2007	SIGMOD	4.1905499e-05
12,580	k-Means Projective Clustering	2004	PODS	4.1905499e-05
12,679	Fast Evaluation Techniques for Complex Similarity Queries	2001	VLDB	4.1905499e-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.0032118946
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018437125
1,596	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011210688
1,755	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB	0.00010661725
2,023	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.7586371e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,062	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6348035e-05
2,023	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.7586371e-05
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
9,026	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	4.4030177e-05
13,581	What's Wrong with High-Dimensional Similarity Search?	2008	VLDB	-
858	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00015833075
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
710	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00017727016
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
1,180	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455619