https://scholars.lib.ntu.edu.tw/handle/123456789/329483
標題: | Fast and versatile algorithm for nearest neighbor search based on a lower bound tree | 作者: | Chen, Yong-Sheng Hung, Yi-Ping Yen, Ting-Fang CHIOU-SHANN FUH |
關鍵字: | Lower bound tree; Nearest neighbor search | 公開日期: | 2007 | 卷: | 40 | 期: | 2 | 起(迄)頁: | 360-375 | 來源出版物: | Pattern Recognition | 摘要: | In this paper, we present a fast and versatile algorithm which can rapidly perform a variety of nearest neighbor searches. Efficiency improvement is achieved by utilizing the distance lower bound to avoid the calculation of the distance itself if the lower bound is already larger than the global minimum distance. At the preprocessing stage, the proposed algorithm constructs a lower bound tree (LB-tree) by agglomeratively clustering all the sample points to be searched. Given a query point, the lower bound of its distance to each sample point can be calculated by using the internal node of the LB-tree. To reduce the amount of lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. For further efficiency improvement, data transformation can be applied to the sample and the query points. In addition to finding the nearest neighbor, the proposed algorithm can also (i) provide the k-nearest neighbors progressively; (ii) find the nearest neighbors within a specified distance threshold; and (iii) identify neighbors whose distances to the query are sufficiently close to the minimum distance of the nearest neighbor. Our experiments have shown that the proposed algorithm can save substantial computation, particularly when the distance of the query point to its nearest neighbor is relatively small compared with its distance to most other samples (which is the case for many object recognition problems). © 2005 Pattern Recognition Society. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-33750379261&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/329483 https://www.scopus.com/inward/record.uri?eid=2-s2.0-33750379261&doi=10.1016%2fj.patcog.2005.08.016&partnerID=40&md5=bf72585252afa52075a7a8dbf9cfb0d8 |
ISSN: | 00313203 | DOI: | 10.1016/j.patcog.2005.08.016 | SDG/關鍵字: | Computational methods; Data transfer; Object recognition; Problem solving; Trees (mathematics); Agglomeratively clustering; Internal nodes; Lower bound trees; Nearest neighbor searches; Algorithms |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。