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

摘要: In this paper, we present a fast and versatile algorithm which can rapidly perform variety of nearest neighbor searches. Efficiency improvement is achieved by utilizing the distance lower bound to avoid calculation itself if already larger than global minimum distance. At preprocessing stage, proposed constructs tree (LB-tree) agglomeratively clustering all sample points be searched. Given query point, its each point calculated using internal node LB-tree. To reduce amount bounds actually calculated, winner-update search strategy used for traversing tree. For further efficiency improvement, data transformation applied points. addition finding neighbor, also (i) provide k-nearest neighbors progressively; (ii) find within specified threshold; (iii) identify whose distances are sufficiently close neighbor. Our experiments have shown that save substantial computation, particularly when relatively small compared with most other samples (which case many object recognition problems).