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

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

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

12 Scopus citations

Abstract

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.

Original languageEnglish
Pages446-453
Number of pages8
DOIs
StatePublished - 12 Sep 2001
Event8th International Conference on Computer Vision - Vancouver, BC, United States
Duration: 9 Jul 200112 Jul 2001

Conference

Conference8th International Conference on Computer Vision
CountryUnited States
CityVancouver, BC
Period9/07/0112/07/01

Fingerprint Dive into the research topics of 'Fast algorithm for nearest neighbor search based on a lower bound tree'. Together they form a unique fingerprint.

Cite this