Winner-update algorithm for nearest neighbor search

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


研究成果: Article同行評審

4 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)704-707
期刊Proceedings - International Conference on Pattern Recognition
出版狀態Published - 1 12月 2000


深入研究「Winner-update algorithm for nearest neighbor search」主題。共同形成了獨特的指紋。