An improved branch and bound algorithm for computing k-nearest neighbors

Experimental results using samples from bivariate Gaussian and uniform distributions suggest that the number of distance computations required by the modified algorithm is typicaly one fourth of that of the Fukunaga-Narendra algorithm.

Abstract

In 1975 Fukunaga and Narendra proposed an efficient branch and bound algorithm for computing k-nearest neighbors. Their algorithm, after a hierarchical decomposition of the design set into disjoint subsets, employs two rules in order to eliminate the necessity of calculating many distances. This correspondence discusses the applicability of two additional rules for a further reduction of the number of distance computations. Experimental results using samples from bivariate Gaussian and uniform distributions suggest that the number of distance computations required by the modified is typicaly one fourth of that of the Fukunaga-Narendra algorithm.