Fast algorithm for nearest neighbor search based on a lower bound tree

Yong-Sheng Chen, Y. P. Hung*, C. S. Fuh

*此作品的通信作者

研究成果: Paper同行評審

15 引文 斯高帕斯(Scopus)

摘要

This paper presents a novel algorithm for fast nearest neighbor search. At the preprocessing stage, the proposed algorithm constructs a lower bound tree by agglomeratively clustering the sample points in the database. Calculation of the distance between the query and the sample points can be avoided if the lower bound of the distance is already larger than the minimum distance. The search process can thus be accelerated because the computational cost of the lower bound, which can be calculated by using the internal node of the lower bound tree, is less than that of the distance. To reduce the number of the lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. Moreover, the query and the sample points can be transformed for further efficiency improvement. Our experiments show that the proposed algorithm can greatly speed up the nearest neighbor search process. When applying to the real database used in Nayar's object recognition system, the proposed algorithm is about one thousand times faster than the exhaustive search.

原文English
頁面446-453
頁數8
DOIs
出版狀態Published - 12 9月 2001
事件8th International Conference on Computer Vision - Vancouver, BC, United States
持續時間: 9 7月 200112 7月 2001

Conference

Conference8th International Conference on Computer Vision
國家/地區United States
城市Vancouver, BC
期間9/07/0112/07/01

指紋

深入研究「Fast algorithm for nearest neighbor search based on a lower bound tree」主題。共同形成了獨特的指紋。

引用此