Fast algorithm for nearest neighbor search based on a lower bound tree
Fast algorithm for nearest neighbor search based on a lower bound tree
- Neue Suche nach: Yong-Sheng Chen,
- Neue Suche nach: Yi-Ping Hung,
- Neue Suche nach: Chiou-Shann Fuh,
- Neue Suche nach: Yong-Sheng Chen,
- Neue Suche nach: Yi-Ping Hung,
- Neue Suche nach: Chiou-Shann Fuh,
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.
Dokumentinformationen
Fast algorithm for nearest neighbor search based on a lower bound tree
Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 ; 1 ; 446-453 vol.1
2001-01-01
864300 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Ähnliche Titel
Fast Algorithm for Nearest Neighbor Search Based on a Lower Bound Tree
| British Library Conference Proceedings | 2001
Fast nearest-neighbor search algorithm [2669-11]
| British Library Conference Proceedings | 1996
Fast multidimensional nearest neighbor search algorithm using priority queue
| Online Contents | 2008
Nearest neighbor search for relevance feedback
| IEEE | 2003