Algorithms for fast vector quantization

"Algorithms for fast vector quantization," Sunil. Arya and David. M. Mount, 1993

The paper presents three algorithms, standard k-d tree search, priority k-d tree search, and neighborhood graph search, for nearest neighbor matching problem which is important in many applications, including vector quantization.

Standard k-d tree is a binary search tree in high dimension. Each internal node of the k-d tree corresponds to a hyperplane orthogonal to one of the coordinate axis which splits a rectangle into two parts, and the leaf nodes store the data points. The algorithm works with incremental distance calculation. That is, compute the squared distance at each leaf node and update the nearest neighbor by finding the corresponding nodes recursively. Priority k-d tree involves a heuristic idea and reduces the complexity by interrupting the search before it terminates. Relative neighborhood graph(RNG) lets two point are adjacent if there is no point that is simultaneously closer to both points than they are to one another. The experiment shows that RNG*-search is fastest of the three algorithm but require twice as much storage than the other, and its complexity is a little higher.