Vector quantization by lazy pairwise nearest neighbor method
Pasi Fra¨nti · Optical Engineering · 1999
The Pairwise Nearest Neighbor (PNN) algorithm is a well-known method for the codebook construction in vector quantization, and for the clustering of data sets. The algorithm has simple structure and it gives high quality solutions. A drawback of the method is the large running time of the original (exact) implementation. In this paper we prove the monotony of the merge costs of the PNN. The monotony property is utilized for speeding-up an existing PNN variant. The idea is to postpone a number of distance calculations. In this way we can reduce the computation by about 35% while preserving the exactness of the PNN.