Analysis and improvement of the partial distance search algorithm

The partial distance search algorithm (PDS) introduced for reducing the computational complexity of the nearest neighbor search in vector quantization is analyzed. In particular, a detailed analysis of the computational savings that can be obtained by minor modifications to this algorithm is performed. A dynamic programming procedure is proposed that automatically determines how often the comparison with the current minimum distance has to be done in order to minimize the expected global cost of the search. The number and position of the comparisons within the distance evaluation loop depend on the ratio of the cost of a comparison operation to that of the partial distance evaluation. It is shown that the two costs are comparable for RISC (reduced instruction set computer) processors, and a 25% speedup with respect to the PDS algorithm is reported for 24 dimension feature vectors used in a continuous-density HMM (hidden Markov model) system with 16 Gaussian mixtures per state.<>