TY - JOUR

T1 - Winner-update algorithm for nearest neighbor search

AU - Chen, Yong-Sheng

AU - Hung, Yi Ping

AU - Fuh, Chiou Shann

PY - 2000/12/1

Y1 - 2000/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34147094359&partnerID=8YFLogxK

U2 - 10.1109/ICPR.2000.906172

DO - 10.1109/ICPR.2000.906172

M3 - Article

AN - SCOPUS:34147094359

SN - 1051-4651

VL - 15

SP - 704

EP - 707

JO - Proceedings - International Conference on Pattern Recognition

JF - Proceedings - International Conference on Pattern Recognition

IS - 2

ER -