An Efficient Branch and Bound Search Algorithm for Computing K Nearest Neighbors in a Multidimensional Vector Space

W. D'Haes (Belgium/France), D. Van Dyck (Belgium), and X. Rodet (France)


pattern recognition, K nearest neighbors, nonparametric estimation, principal component analysis


An efficient branch and bound search algorithm is proposed for the computation of the K nearest neighbors in a multi dimensional vector space. In a preprocessing step, the sam ple of feature vectors is decomposed hierarchically using hyperplanes determined by principal component analysis (PCA). During the search of the nearest neighbors, the tree that represents this decomposition is traversed in depth first order avoiding nodes that cannot contain nearest neighbors. The behavior of the algorithm is studied on artificial data.

Important Links:

Go Back