Efficient nearest neighbor search in high dimensional hamming space

doi:10.1016/j.patcog.2019.107082

CASIA OpenIR > 多模态人工智能系统全国重点实验室 > 先进时空数据分析与学习

	Efficient nearest neighbor search in high dimensional hamming space
	Fan, Bin1,2,3 ; Kong, Qingqun2,3 ; Zhang, Baoqian 1,4; Liu, Hongmin 5,6; Pan, Chunhong1,2 ; Lu, Jiwen 7
发表期刊	PATTERN RECOGNITION
ISSN	0031-3203
	2020-03-01
卷号	99 页码:11
通讯作者	Liu, Hongmin(hmliu_82@163.com)
摘要	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.
关键词	Binary feature Feature matching Approximate nearest neighbor search Scalable image matching
DOI	10.1016/j.patcog.2019.107082
关键词[WOS]	ALGORITHM
收录类别	SCI
语种	英语
资助项目	National Science Foundation of China[61573352,61876180] ; Young Elite Scientists Sponsorship Program by CAST[2018QNRC001] ; National Science Foundation of China[61573352,61876180] ; Young Elite Scientists Sponsorship Program by CAST[2018QNRC001]
项目资助者	National Science Foundation of China ; Young Elite Scientists Sponsorship Program by CAST
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Engineering, Electrical & Electronic
WOS记录号	WOS:000504503500002
出版者	ELSEVIER SCI LTD
七大方向——子方向分类	模式识别基础
引用统计	被引频次：11[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/29458
专题	多模态人工智能系统全国重点实验室_先进时空数据分析与学习
通讯作者	Liu, Hongmin
作者单位	1.Natl Lab Pattern Recognit, Beijing, Peoples R China 2.Chinese Acad Sci, Inst Automat, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Beijing, Peoples R China 4.China Foreign Affairs Univ, Beijing, Peoples R China 5.Univ Sci & Technol Beijing, Sch Automat & Elect Engn, Beijing 100083, Peoples R China 6.Henan Polytech Univ, Sch Comp Sci & Technol, Jiaozuo 454000, Henan, Peoples R China 7.Tsinghua Univ, Beijing, Peoples R China
第一作者单位	模式识别国家重点实验室; 中国科学院自动化研究所
推荐引用方式 GB/T 7714	Fan, Bin,Kong, Qingqun,Zhang, Baoqian,et al. Efficient nearest neighbor search in high dimensional hamming space[J]. PATTERN RECOGNITION,2020,99:11.
APA	Fan, Bin,Kong, Qingqun,Zhang, Baoqian,Liu, Hongmin,Pan, Chunhong,&Lu, Jiwen.(2020).Efficient nearest neighbor search in high dimensional hamming space.PATTERN RECOGNITION,99,11.
MLA	Fan, Bin,et al."Efficient nearest neighbor search in high dimensional hamming space".PATTERN RECOGNITION 99(2020):11.