A Branch and Bound Algorithm for Computing k-Nearest Neighbors
- 1 July 1975
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-24 (7) , 750-753
- https://doi.org/10.1109/t-c.1975.224297
Abstract
Computation of the k-nearest neighbors generally requires a large number of expensive distance computations. The method of branch and bound is implemented in the present algorithm to facilitate rapid calculation of the k-nearest neighbors, by eliminating the necesssity of calculating many distances. Experimental results demonstrate the efficiency of the algorithm. Typically, an average of only 61 distance computations were made to find the nearest neighbor of a test sample among 1000 design samples.Keywords
This publication has 5 references indexed in Scilit:
- The condensed nearest neighbor rule (Corresp.)IEEE Transactions on Information Theory, 1968
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967
- Branch-and-Bound Methods: A SurveyOperations Research, 1966
- Backtrack ProgrammingJournal of the ACM, 1965
- A Nonparametric Estimate of a Multivariate Density FunctionThe Annals of Mathematical Statistics, 1965