Survey of Nearest Neighbor Techniques

By null Vandana, N. Bhatia. arXiv.org, 2010

634 citations recorded by the source corpus.

The nearest neighbor (NN) technique is very simple, highly efficient and effective in the field of pattern recognition, text categorization, object recognition etc. Its simplicity is its main advantage, but the disadvantages can't be ignored even. The memory requirement and computation complexity also matter. Many techniques are developed to overcome these limitations. NN techniques are broadly classified into structure less and structure based techniques. In this paper, we present the survey of such techniques. Weighted kNN, Model based kNN, Condensed NN, Reduced NN, Generalized NN are structure less techniques whereas k-d tree, ball tree, Principal Axis Tree, Nearest Feature Line, Tunable NN, Orthogonal Search Tree are structure based algorithms developed on the basis of kNN. The structure less method overcome memory limitation and structure based techniques reduce the computational complexity.

Subfields: Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/ca2bfcf88873cce70e92b160bf0b6a2472c2fee7

How researchers see this paper

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

In Computer Vision and Pattern Recognition

Citations in the corpus

Dense Text Retrieval Based on Pretrained Language Models: A Survey (2022, background): “Given a collection of candidate text embeddings P (P ⊂ R and |P| = m) and a query embedding q ∈ R, the goal of nearest neighbor search [248], [249] is to efficiently search for p ∈ P that are most close to q, i.”
Submodularity in Data Subset Selection and Active Learning (2015, methodology): “Though extremely simple, the NN classifier has been applied on a number of machine learning tasks, including hand-written digit recognition, text categorization, object recognition, etc (Bhatia et al., 2010; Boiman et al., 2008; Shah et al., 2011).”
Effects of Distance Measure Choice on K-Nearest Neighbor Classifier Performance: A Review (2017, positive): “4 Thus, KNN comprises the baseline classiﬁer in many pattern classi-ﬁcation problems such as pattern recognition, 5 text categorization, 6 ranking models, 7 object recognition, 8 and event recognition 9 applications.”
Traffic prediction in a bike-sharing system (2015, methodology): “We predict the entire traffic of the city first and then allocate the entire traffic to each cluster based on the check-out proportion across clusters, which is predicted by KNN prediction [3].”
Fast geometric learning with symbolic matrices (2020, neutral): “When the datasets ( x i ) and ( y j ) have a small intrinsic dimension, efﬁcient schemes can outperform brute-force approaches [11, 31, 49, 53, 65, 77, 85].”
Classification of Heart Disease Using K- Nearest Neighbor and Genetic Algorithm (2015, neutral): “Structure based NN techniques are based on structures of data like orthogonal structure tree (OST), ball tree, k-d tree, axis tree, nearest future line and central line [5].”