When Is ''Nearest Neighbor'' Meaningful?

By K. Beyer, J. Goldstein, Raghu Ramakrishnan, U. Shaft. 1999

Subfields: Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Unsupervised Progressive Learning and the STAM Architecture (2019, background): “Its effectiveness, however, gradually drops as the input dimensionality increases [ Beyer et al. , 1999 ] .”
A survey on unsupervised outlier detection in high‐dimensional numerical data (2012, background): “12,29, if a data set is composed of many natural groupings or clusters, each following their own distribution, then the concentration effect will typically be less severe for queries based on points within a cluster of similar points generated according to the same mechanism, especially when the…”
Water quality prediction using machine learning models based on grid search method (2023, unknown): “Nevertheless, KNN is not recommended for big datasets because it does all computation throughout testing and converges during all trained data, calculating the closest neighbor each time [33].”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, background): “Evidence suggests that when the representational dimension of feature vectors is high (roughly 20 or more [5], [49]), traditional similarity search accesses an unacceptably-high proportion of the data elements, unless the underlying data distribution has special properties [6], [12], [41].”
"I know it when I see it". Visualization and Intuitive Interpretability (2017, background): “Beyond this general in-accessibility, however, high-dimensional vector spaces also speciﬁcally impede interpretation, as distances between data points have a tendency to lose their meaning (Beyer et al., 1999) – this is commonly known as the “curse of dimensionality”.”
Efficient similarity search and classification via rank aggregation (2003, methodology): “For some recent theoretical work, see [18, 16, 19]; for recent theoretical/applied work, see [13, 1 , 12, 5, 4, 20].”
Defining cell types and states with single-cell genomics (2015, background): “Specifically, the distance between a point and itsmost distant neighbor approaches the distance between the point and its nearest neighbor (Beyer et al. 1999).”
A Survey of Clustering Data Mining Techniques (2006, background): “Mathematically, nearest neighbor query becomes unstable: the distance to the nearest neighbor becomes indistinguishable from the distance to the majority of points [Beyer et al. 1999].”