TREE SEARCH TECHNIQUE FOR THE OPTIMIZATION OF THE k NEAREST NEIGHBORS ALGORITHM

Computation of the k nearest neighbors of an unknown pattern generally requires a large number of expensive distance computations. The method nicknamed PURD presented in this paper is proposed to speed-up this task. It is based on a study of Portegys and uses the concept of relative distance between two patterns, PURD consists in a reorganization of a database as a tree structure, followed by a tree search based on rules which allows portions of the tree to be cut-off. The price to pay is an increase of the amount of memory needed to store preprocessed data. This technique has been used in a handwriting recognition multi-agent system to classify digit samples derived from NIST data. Experimental results demonstrate the efficiency of the proposed algorithm. A speed-up of more than an order of magnitude has been obtained against classical kNN for the same rate of recognition. In comparison to other computational time optimization methods, PURD performances are quite interesting.