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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2001-01-01


    Size :

    864300 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Fast Algorithm for Nearest Neighbor Search Based on a Lower Bound Tree

    Chen, Y. / Hung, Y. / Fuh, C. et al. | British Library Conference Proceedings | 2001


    Fast nearest-neighbor search algorithm [2669-11]

    Darwish, A. M. / SPIE | British Library Conference Proceedings | 1996



    Nearest neighbor search for relevance feedback

    Tesic, J. / Manjunath, B.S. | IEEE | 2003


    Nearest Neighbor Search for Relevance Feedback

    Tesic, J. / Manjunath, B. / IEEE | British Library Conference Proceedings | 2003