[Reading] Algorithms for Fast Vector Quantization

Finding the nearest neighbor (NN) is a problem of significant importance in many applications. One important application is vector quantization, a technique used in the compression of speech and images. If one is willing to relax the requirement of finding the true NN, this paper shows that it is possible to achieve significant improvements in running time and at only a very small loss in the performance of the vector quantizer.

This paper present an empirical study of 3 NN algorithms on a number of data distributions, and in dimensions varying from 8 to 16.
(1) Standard k-d tree algorithm, which has been enhanced to use incremental distance calculation.
(2) Priority k-d tree search, a further improvement that orders search by the proximity of the k-d cell to the query point.
(3) A neighborhood graph search algorithm, based on a simple greedy search.