Efficient nearest neighbor search in high dimensional hamming space
Efficient nearest neighbor search in high dimensional hamming space
复制标题
高维汉明空间中的高效最近邻搜索
DOI：
10.1016/j.patcog.2019.107082
复制
发表时间：
2020-03-01
影响因子：
8
通讯作者：
Lu, Jiwen
中科院分区：
文献类型：
--
作者：
Fan, Bin;Kong, Qingqun;Lu, Jiwen
对于实值向量的快速近似最近邻搜索已经得到了很好的研究，但是对于二值描述符的快速近似最近邻搜索方法还不太成熟。本文利用欧几里得空间中成熟的技术来解决这个问题。为此，首先将二值描述子映射为低维浮点向量，在映射的欧几里得空间中尽可能保留原Hamming空间中的邻域信息。然后，利用KD-Tree对映射的欧几里得空间进行分区，以快速找到给定查询点的近似近邻。这相当于利用邻域保持的性质，在原Hamming空间中过滤出一个最近邻候选子集。最后，对少量候选对象进行Hamming排序，以在原始Hamming空间中找到近似最近的邻居，与蛮力线性扫描相比，运行时间仅为一小部分。我们的实验表明，所提出的方法显著优于目前的技术水平，在各种加速因素下获得了更高的搜索精度，例如，当搜索速度比100万数据库的线性扫描快200倍时，搜索精度比以前的方法提高了至少16%（从67.7%提高到83.7%）。(C) 2019 Elsevier Ltd.版权所有。
Fast approximate nearest neighbor search has been well studied for real-valued vectors, however, the methods for binary descriptors are less developed. The paper addresses this problem by resorting to the well established techniques in Euclidean space. To this end, the binary descriptors are firstly mapped into low dimensional float vectors under the condition that the neighborhood information in the original Hamming space could be preserved in the mapped Euclidean space as much as possible. Then, KD-Tree is used to partitioning the mapped Euclidean space in order to quickly find approximate nearest neighbors for a given query point. This is identical to filter out a subset of nearest neighbor candidates in the original Hamming space due to the property of neighborhood preserving. Finally, Hamming ranking is applied to the small number of candidates to find out the approximate nearest neighbor in the original Hamming space, with only a fraction of running time compared to the bruteforce linear scan. Our experiments demonstrate that the proposed method significantly outperforms the state of the arts, obtaining improved search accuracy at various speed up factors, e.g., at least 16% improvement of search accuracy over previous methods (from 67.7% to 83.7%) when the search speed is 200 times faster than the linear scan for a one million database. (C) 2019 Elsevier Ltd. All rights reserved.