Practical methods for speeding-up the pairwise nearest neighbor method

The pairwise nearest neighbor (PNN) method is a simple and well-known metho d for codebook generation in vector quantization. In its exact form, it pro vides a good-quality codebook but at the cost of high run time. A fast exac t algorithm was recently introduced to implement the PNN an order of magnit ude faster than the original O((NK)-K-3) time algorithm. The run time, howe ver, is still lower bounded by O((NK)-K-2), and therefore, additional speed -ups may be required in applications where time is an important factor. We consider two practical methods to reduce the amount of work caused by the d istance calculations. Through experiments, we show that the run time can be reduced to 10 to 15% that of the original method for data sets in color qu antization and in spatial vector quantization. (C) 2001 Society of Photo-Op tical Instrumentation Engineers.