Source-linked AI summary
Survey of Nearest Neighbor Techniques
Nitin Bhatia, Vandana
TL;DR
Nearest-neighbor methods are useful but face memory and computational limitations. The paper surveys structure-less and structure-based techniques developed from kNN. Structure-less methods address memory limitation, while structure-based methods reduce computational complexity, with suitability depending on circumstances.
Problem
Nearest-neighbor methods are simple and effective, but memory requirements and computational complexity remain important limitations.
Method
The paper surveys structure-less and structure-based nearest-neighbor techniques developed from kNN.
Results
Structure-less methods overcome memory limitation, whereas structure-based methods reduce computational complexity.
Takeaways & Limitations
Different nearest-neighbor techniques provide improvements in speed or space efficiency and are suitable under particular circumstances.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Nearest neighbor methods classify unknown data using labeled nearby points and are widely applied, but memory requirements and computational complexity motivate numerous kNN improvements and faster structured searches.
- Nearest neighbor classification assigns an unknown data point the class of a nearest point whose class is known.
- The rule is used in pattern recognition, text categorization, ranking, object recognition, and event recognition.
- kNN extends nearest-neighbor classification by using a value of k to determine how many neighbors define a sample’s class.
- Weighted kNN assigns distance-based weights, while model-based kNN automatically selects k.
- Ball trees, k-d trees, nearest feature lines, tunable metrics, principal axis trees, and orthogonal search trees organize data to increase kNN speed.
II. NEAREST NEIGHBOR TECHNIQUES
Nearest-neighbor techniques are organized into structure-less and structure-based methods, with the former reducing stored data and the latter organizing data to accelerate search.
- Nearest-neighbor techniques are divided into structure-less and structure-based categories.
- Structure less NN techniques: Basic kNN evaluates distances from a query point to all training points and selects the point with the lowest distance.
- Structure less NN techniques: Weighted, condensed, reduced, model-based, generalized, modified, and clustered variants address weighting, redundancy, k selection, or computational limitations.
- Structure based NN techniques: Ball trees, k-d trees, principal axis trees, orthogonal search trees, nearest feature lines, tunable metrics, and center lines structure data or distances for faster search.
- Limitations: The techniques also have boundaries, including computational complexity, difficult threshold selection, query-time costs, and failures under particular geometric conditions.
- Comparison of techniques: Reported method-specific outcomes include improved classification accuracy for k-d trees, robustness for modified kNN, and effective performance for some small or large datasets.
III. CONCLUSION
The survey compares structure-less and structure-based nearest-neighbor methods as improvements to basic kNN, with different techniques suited to particular circumstances.
- The survey compares structure-less and structure-based nearest-neighbor techniques as improvements over basic kNN.
- The reported improvements target speed efficiency and space efficiency, while each technique is suitable under particular circumstances.