Practical methods for speeding-up the pairwise nearest neighbor method

Olli Virmajoki; Pasi Franti; Timo Kaukoranta

doi:10.1117/1.1412423

1 November 2001 Practical methods for speeding-up the pairwise nearest neighbor method

Olli Virmajoki, Pasi Franti, Timo Kaukoranta

Optical Engineering, Vol. 40, Issue 11, (November 2001). https://doi.org/10.1117/1.1412423

The pairwise nearest neighbor (PNN) method is a simple and well-known method for codebook generation in vector quantization. In its exact form, it provides a good-quality codebook but at the cost of high run time. Afast exact algorithm was recently introduced to implement the PNN an order of magnitude faster than the original O(N3K) time algorithm. The run time, however, is still lower bounded by O(N2K), 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 distance 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 quantization and in spatial vector quantization.

©(2001) Society of Photo-Optical Instrumentation Engineers (SPIE)

Citation Download Citation

Olli Virmajoki, Pasi Franti, and Timo Kaukoranta "Practical methods for speeding-up the pairwise nearest neighbor method," Optical Engineering 40(11), (1 November 2001). https://doi.org/10.1117/1.1412423

Published: 1 November 2001

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available