Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search
Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search
复制标题
用于最近邻搜索的查询自适应倒数哈希表
DOI：
10.1109/tip.2015.2505180
复制
发表时间：
2016-02-01
影响因子：
10.6
通讯作者：
Li, Xuelong
中科院分区：
文献类型：
--
作者：
Liu, Xianglong;Deng, Cheng;Li, Xuelong
近年来，二进制哈希技术在近似近邻搜索中取得了成功。在实践中，通常使用散列构建多个散列表，以覆盖每个表的hit bucket中更多期望的结果。然而，很少有研究使用任何类型的哈希算法构建多个信息哈希表的统一方法。同时，对于多表搜索，它还缺乏一种通用的自适应查询和细粒度排序方案，可以减轻标准哈希技术中遭受的二进制量化损失。为了解决上述问题，在本文中，我们首先将表构造视为一组候选哈希函数的选择问题。利用函数集的图表示，我们提出了一个有效的解决方案，即依次应用归一化优势集来寻找每个表的信息量最大且最独立的哈希函数。为了进一步减少表之间的冗余，我们以一种增强的方式探索了互反哈希表，其中哈希函数图以高权重更新，强调了先前哈希表的错误分类邻居对。为了从查询中细化在一定汉明半径内检索到的桶的排名，我们提出了一种自适应查询的按位加权方案，利用其哈希函数及其补集的判别能力进行最近邻搜索，从而在每个哈希表中实现细粒度的桶排名。此外，我们在自适应加权汉明半径内使用快速且倒数的表查找算法将该方案集成到多表搜索中。在本文中，构造方法和查询自适应搜索方法都是通用的，并且兼容使用不同特征空间和/或参数设置的不同类型的哈希算法。我们在几个大规模基准测试上的广泛实验表明，所提出的技术可以显著优于朴素构造方法和最先进的哈希算法。
Recent years have witnessed the success of binary hashing techniques in approximate nearest neighbor search. In practice, multiple hash tables are usually built using hashing to cover more desired results in the hit buckets of each table. However, rare work studies the unified approach to constructing multiple informative hash tables using any type of hashing algorithms. Meanwhile, for multiple table search, it also lacks of a generic query-adaptive and fine-grained ranking scheme that can alleviate the binary quantization loss suffered in the standard hashing techniques. To solve the above problems, in this paper, we first regard the table construction as a selection problem over a set of candidate hash functions. With the graph representation of the function set, we propose an efficient solution that sequentially applies normalized dominant set to finding the most informative and independent hash functions for each table. To further reduce the redundancy between tables, we explore the reciprocal hash tables in a boosting manner, where the hash function graph is updated with high weights emphasized on the misclassified neighbor pairs of previous hash tables. To refine the ranking of the retrieved buckets within a certain Hamming radius from the query, we propose a query-adaptive bitwise weighting scheme to enable fine-grained bucket ranking in each hash table, exploiting the discriminative power of its hash functions and their complement for nearest neighbor search. Moreover, we integrate such scheme into the multiple table search using a fast, yet reciprocal table lookup algorithm within the adaptive weighted Hamming radius. In this paper, both the construction method and the query-adaptive search method are general and compatible with different types of hashing algorithms using different feature spaces and/or parameter settings. Our extensive experiments on several large-scale benchmarks demonstrate that the proposed techniques can significantly outperform both the naive construction methods and the state-of-the-art hashing algorithms.