Name
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 winner-update algorithm can also speed up the search for k nearest neighbors, neighbors within a specified distance threshold, and neighbors close to the nearest neighbor |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/ICPR.2000.906172 | ICPR |
Keywords | Field | DocType |
optimisation,pattern recognition,minkowski inequality,search problems,query point,nearest neighbor search,winner-update algorithm,lower bound,computational complexity,data compression,nearest neighbor,testing,information science,acceleration,computer science,metric space,binary search trees,information retrieval | k-nearest neighbors algorithm,R-tree,Fixed-radius near neighbors,Pattern recognition,Computer science,Best bin first,Algorithm,Nearest neighbor graph,Artificial intelligence,Large margin nearest neighbor,Cover tree,Nearest neighbor search | Conference |
Volume | ISSN | ISBN |
2 | 1051-4651 | 0-7695-0750-6 |
Citations | PageRank | References |
5 | 0.55 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yong-Sheng Chen | 1 | 314 | 30.12 |
| Yi-Ping Hung | 2 | 1743 | 168.25 |
| Chiou-Shann Fuh | 3 | 647 | 56.08 |