Termination conditions for a fast k-nearest neighbor method

A method for reducing the computation cost of searching k-NNs on the basis of the branch-and-bound algorithm while not considering the computation time required for pre-processing is proposed.

Abstract

One of the popular recognition methods is the k-nearest neighbor (follows k-NN) method. In this method, however, when the number of training samples is large, the computation cost increases in proportion to the size of the samples. Therefore, we propose a method for reducing the computation cost of searching k-NNs on the basis of the branch-and-bound algorithm (K. Fukunaga and P.M. Narendra, 1975). The aim of the study was to reduce the computation time required for recognition while not considering the computation time required for pre-processing. In our method, we add some conditions for terminating the procedure when the true k-NNs are found. We show the effectiveness of these conditions using real data.