Title :
Evaluation of fast algorithms for finding the nearest neighbor
Author :
Lubiarz, Stephane ; Lockwood, Philip
Author_Institution :
Dept. of Speech Process., Matra Commun., Bois d´´Arcy, France
Abstract :
In speech recognition systems as well as in speech coders using vector quantization, the search for the nearest neighbor is a computationally intensive task. We address the problem of fast nearest neighbour search. State of the art solutions tend to approach logarithmic access time. The problem is that such performance is generally achieved at the expense of a significant increase in storage requirements. We compare several known approaches and propose new extensions. These new contributions allows for a significant reduction in memory requirements without impacting the performance in terms of number of distances computed and optimality of the search
Keywords :
search problems; speech coding; speech recognition; vector quantisation; vocoders; VQ; distances; fast algorithms; fast nearest neighbour search; logarithmic access time; memory requirements reduction; nearest neighbor; performance; speech coders; speech recognition systems; storage requirements; vector quantization; Clustering algorithms; Code standards; Costs; Data structures; Euclidean distance; Hidden Markov models; Nearest neighbor searches; Speech processing; Speech recognition; Vector quantization;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1997. ICASSP-97., 1997 IEEE International Conference on
Conference_Location :
Munich
Print_ISBN :
0-8186-7919-0
DOI :
10.1109/ICASSP.1997.596232