Winner-update algorithm for nearest neighbor search

Yong-Sheng Chen*, Yi Ping Hung, Chiou Shann Fuh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

This paper presents an algorithm, called the winner-update algorithm, for accelerating the nearest neighbor search. By constructing a hierarchical structure for each feature point in the lp metric space, this algorithm can save a large amount of computation at the expense of moderate preprocessing and twice the memory storage. Given a query point, the cost for computing the distances from this point to all the sample points can be reduced by using a lower bound list of the distance established from Minkowski's inequality. Our experiments have shown that the proposed algorithm can save a large amount of computation, especially when the distance between the query point and its nearest neighbor is relatively small. With slight modification, the winnerupdate algorithm can also speed up the search for k nearest neighbors, neighbors within a specified distance threshold, and neighbors close to the nearest neighbor.

Original languageEnglish
Pages (from-to)704-707
Number of pages4
JournalProceedings - International Conference on Pattern Recognition
Volume15
Issue number2
DOIs
StatePublished - 1 Dec 2000

Fingerprint Dive into the research topics of 'Winner-update algorithm for nearest neighbor search'. Together they form a unique fingerprint.

Cite this