A high-speed search algorithm for vector quantization

In this work, we present a very efficient search method useful for vector quantization, and other nearest neighbor search problems. The algorithm first finds a small area around the input vector with one codevector on its boundary. After finding such an area, the codebook is searched to determine whether there is any other codeword inside this area or not. This search is performed employing two tests, avoiding distortion calculation for those codewords which fail these tests. Using this algorithm the saving in the number of multiplications can be over 99%, in comparison with the conventional full search method, with the number of additions being reduced by as much as 82%. The price paid is a moderate increase in the number of comparisons.