Fast and versatile algorithm for nearest neighbor search based on a lower bound tree
Fast and versatile algorithm for nearest neighbor search based on a lower bound tree
复制标题
DOI：
10.1016/j.patcog.2005.08.016
复制
发表时间：
2007-02-01
影响因子：
8
通讯作者：
Fuh, Chiou-Shann
中科院分区：
文献类型：
--
作者：
Chen, Yong-Sheng;Hung, Yi-Ping;Fuh, Chiou-Shann
在本文中，我们提出了一种快速且通用的算法，它能够快速执行各种最近邻搜索。通过利用距离下限来提高效率，如果下限已经大于全局最小距离，就避免计算距离本身。在预处理阶段，所提出的算法通过对所有要搜索的样本点进行凝聚聚类来构建一棵下限树（LB - 树）。给定一个查询点，可以利用LB - 树的内部节点计算它到每个样本点的距离下限。为了减少实际计算的下限数量，采用胜者更新搜索策略来遍历树。为了进一步提高效率，可以对样本点和查询点进行数据变换。除了找到最近邻，所提出的算法还能够（i）逐步提供k个最近邻；（ii）在指定的距离阈值内找到最近邻；（iii）识别那些到查询点的距离与最近邻的最小距离足够接近的邻居。我们的实验表明，所提出的算法能够节省大量计算，特别是当查询点到其最近邻的距离与其到大多数其他样本的距离相比相对较小时（许多目标识别问题都是这种情况）。（c）2005模式识别学会。由爱思唯尔有限公司出版。保留所有权利。
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 agglorneratively 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). (c) 2005 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.