Fast nearest neighbor (NN) finding has been extensively studied. While some fast NN algorithms using metrics rely on the essential properties of metric spaces, the others using non-metric measures fail for large-size templates. However in some applications with very large size templates, the best performance is achieved by NN methods based on the dissimilarity measures resulting in a special space where computations cannot be pruned by the algorithms based-on the triangular inequality. For such NN methods, the existing fast algorithms except condensing algorithms are not applicable. In this paper, a fast hierarchical search algorithm is proposed to find k-NNs using a non-metric measure in a binary feature space. Experiments with handwritten digit recognition show that the new algorithm reduces on average dissimilarity computations by more than 90% while losing the accuracy by less than 0.1%, with a 10% increase in memory.
A fast algorithm for finding k-nearest neighbors with non-metric dissimilarity
2002-01-01
320800 byte
Conference paper
Electronic Resource
English
A Fast Algorithm for Finding k-Nearest Neighbors with Non-Metric Dissimilarity
British Library Conference Proceedings | 2002
|IMPROVING TRUST IN DEEP NEURAL NETWORKS WITH NEAREST NEIGHBORS
TIBKAT | 2020
|Application of Quantum-Based K-Nearest Neighbors Algorithm in Optical Fiber Classification
Springer Verlag | 2023
|