Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search | |
Liu, Xianglong1; Deng, Cheng2; Lang, Bo1; Tao, Dacheng3; Li, Xuelong4; Deng, C | |
作者部门 | 光学影像学习与分析中心 |
2016-02-01 | |
发表期刊 | IEEE TRANSACTIONS ON IMAGE PROCESSING |
ISSN | 1057-7149 |
卷号 | 25期号:2页码:907-919 |
产权排序 | 4 |
摘要 | 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. |
文章类型 | Article |
关键词 | Locality Sensitive Hashing Bit Selection Complementary Hash Tables Query Adaptive Nearest Neighbor Search |
学科领域 | Computer Science, Artificial Intelligence |
WOS标题词 | Science & Technology ; Technology |
DOI | 10.1109/TIP.2015.2505180 |
收录类别 | SCI ; EI |
关键词[WOS] | CODE RANKING ; QUANTIZATION |
语种 | 英语 |
WOS研究方向 | Computer Science ; Engineering |
项目资助者 | National Natural Science Foundation of China(61402026 ; National High Technology Research and Development Program of China(2013AA01A602) ; Program for New Century Excellent Talents in University(NCET-12-0917) ; Fundamental Research Funds for the Central Universities(K5051302019 ; Australian Research Council(DP-140102164 ; 61572388) ; SKLSDE-2014ZX-07 ; FT-130101457) ; SKLSDE-2015ZX-04) |
WOS类目 | Computer Science, Artificial Intelligence ; Engineering, Electrical & Electronic |
WOS记录号 | WOS:000368938400003 |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.opt.ac.cn/handle/181661/27799 |
专题 | 光谱成像技术研究室 |
通讯作者 | Deng, C |
作者单位 | 1.Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China 2.Xidian Univ, Sch Elect Engn, Xian 710071, Peoples R China 3.Univ Technol Sydney, Ctr Quantum Computat & Intelligent Syst, Fac Engn & Informat Technol, Sydney, NSW 2007, Australia 4.Chinese Acad Sci, State Key Lab Transient Opt & Photon, Ctr Opt Imagery Anal & Learning, Xian Inst Opt & Precis Mech, Xian 710119, Peoples R China |
推荐引用方式 GB/T 7714 | Liu, Xianglong,Deng, Cheng,Lang, Bo,et al. Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search[J]. IEEE TRANSACTIONS ON IMAGE PROCESSING,2016,25(2):907-919. |
APA | Liu, Xianglong,Deng, Cheng,Lang, Bo,Tao, Dacheng,Li, Xuelong,&Deng, C.(2016).Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search.IEEE TRANSACTIONS ON IMAGE PROCESSING,25(2),907-919. |
MLA | Liu, Xianglong,et al."Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search".IEEE TRANSACTIONS ON IMAGE PROCESSING 25.2(2016):907-919. |
条目包含的文件 | ||||||
文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
Query-Adaptive Recip(3400KB) | 期刊论文 | 作者接受稿 | 限制开放 | CC BY-NC-SA | 请求全文 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论