Nearest Neighbor

By Eamonn J. Keogh. 2010

754 citations recorded by the source corpus.

Subfields: Evaluation & Benchmarks, Signal Processing

How researchers see this paper

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

In Evaluation & Benchmarks

In Signal Processing

Citations in the corpus

Aggregating Local Image Descriptors into Compact Codes (2012, neutral): “Approximate nearest neighbors search methods [36], [17], [37], [11], [18] are required to handle large databases in computer vision applications [38].”
Product Quantization for Nearest Neighbor Search (2011, background): “Nearest neighbor search is inherently expensive due to the curse of dimensionality [1], [2].”
Angle-based outlier detection in high-dimensional data (2008, background): “One of the most thoroughly discussed effects of this malediction of mining high-dimensional data is that concepts like proximity, distance, or nearest neighbor become less meaningful with increasing dimensionality of data sets [7, 13, 1].”
K-means properties on six clustering benchmark datasets (2018, background): “The cause for this is credited to the “dimensionality curse”, referring either to the sparseness of the data space [53], or that the distances become uniform as dimensions increase [22].”
SMOTE for high-dimensional class-imbalanced data (2013, neutral): “Similar results were described by others [33,34].”
Machine Learning in Wireless Sensor Networks: Algorithms, Strategies, and Applications (2014, background): “In [38], it has been shown that the k-NN algorithm may provide inaccurate results when analyzing problems with high-dimensional spaces (more than 10–15 dimensions) as the distance to different data samples becomes invariant (i.”
Density-Based Projected Clustering of Data Streams (2012, background): “For such kinds of data with higher dimensions, distances grow more and more alike due to an effect termed curse of dimensionality [5] (cf.”
The advantages of the Matthews correlation coefficient (MCC) over F1 score and accuracy in binary classification evaluation (2020, methodology): “We employed machine learning binary classifiers to predict patients and healthy controls in this dataset: gradient boosting [107], decision tree [108], k-nearest neighbors (k-NN) [109], support vector machine (SVM) with linear kernel [7], and support vector machine with radial Gaussian kernel [7].”
Searching with expectations (2010, background): “Nearest neighbor (NN) search is inherently expensive due to the curse of dimensionality [2, 1].”
Model-based mean square error estimators for k-nearest neighbour predictions and applications using remotely sensed data for forest inventories (2009, methodology): “A popular choice in forest inventory is the non-parametric and distribution free k-nearest neighbour method, or knn (Alt, 2001).”
DBSCAN Revisited, Revisited (2017, background): “Independent of the algorithm, the parameter ε of DBSCAN becomes hard to choose in highdimensional data due to the loss of contrast in distances [9, 25, 48].”
Distance geometry and data science (2019, background): “Among the cases where it does apply, we find k-NN: in their experiments, the authors of [26] find that k-NN becomes unstable already in the range n ∈ {10, 20} dimensions.”
Searching with quantization: approximate nearest neighbor search using short codes and distance estimators (2009, positive): “It has been successfully used for local descriptors [10] and 3D object indexing [11, 9].”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, background): “(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].”
The Matthews correlation coefficient (MCC) is more reliable than balanced accuracy, bookmaker informedness, and markedness in two-class confusion matrix evaluation (2021, methodology): “We used four machine learning binary classifiers to predict patients and healthy controls in this dataset: Decision Tree [61], k-Nearest Neighbors (k-NN) [62], Naïve Bayes [63], and Support Vector Machine with radial Gaussian kernel [64].”
Efficient k-nearest neighbor graph construction for generic similarity measures (2011, background): “Fortunately, all datasets we experimented with, and actually most real-life datasets where K-NN is meaningful [3], are of relatively low dimensionality.”
"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”.”