An Efficient Nearest Neighbor Search Method

A simple, but efficient, nearest neighbor search algorithm is proposed and simulation results demonstrating its effectiveness in the case of vector quantization for a given source are presented. The simulation results indicate that use of this approach reduces the number of multiplications and additions to as low as 9 percent of those required for the conventional full search method. The reduction in the number of subtractions is also considerable. The increase in the number of comparisons is moderate, and therefore, the total number of operations can be as low as 28 percent of those required by the full search method. An additional advantage of the described algorithm is the fact that it requires no precomputations and/or extra memory.