Fast implementation of the optimal PNN method

We consider the codebook generation problem involved in the design of a vector quantizer. The aim is to find M code vectors (codebook) for a given set of N training vectors (training set) by minimizing the average pairwise distance between the training vectors and their representative code vectors. Straightforward implementation of the optimal pairwise nearest neighbor (PNN) takes O(N³) time, which is rather slow in many practical situations. Fortunately much faster implementation can be obtained with rather simple modifications to the basic algorithm. We propose a fast O(τN²) time implementation of the optimal PNN, where τ is observed to be significantly smaller than N in practice. We give all necessary data structures and implementation details, and give time complexity of the algorithm both in the best and in the worst case. The proposed implementation achieves the results of the optimal PNN with the same O(N) memory requirement