中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 自动化研究所
  3. 中国科学院自动化研究所
  4. 多模态人工智能系统全国重点实验室
  5. 遥感图像处理团队
Efficient nearest neighbor search in high dimensional hamming space

文献类型：期刊论文

作者Fan, Bin1,2,7; Kong, Qingqun1,2; Zhang, Baoqian3,7; Liu, Hongmin4,5; Pan, Chunhong1,7; Lu, Jiwen6
刊名PATTERN RECOGNITION
出版日期2020-03-01
卷号99页码:11
ISSN号0031-3203
关键词Binary feature Feature matching Approximate nearest neighbor search Scalable image matching
DOI10.1016/j.patcog.2019.107082
通讯作者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.
WOS关键词ALGORITHM
资助项目National Science Foundation of China[61573352,61876180] ; Young Elite Scientists Sponsorship Program by CAST[2018QNRC001]
WOS研究方向Computer Science ; Engineering
语种英语
出版者ELSEVIER SCI LTD
WOS记录号WOS:000504503500002
资助机构National Science Foundation of China ; Young Elite Scientists Sponsorship Program by CAST
源URL[http://ir.ia.ac.cn/handle/173211/29457]  
专题自动化研究所_模式识别国家重点实验室_遥感图像处理团队
通讯作者Liu, Hongmin
作者单位1.Chinese Acad Sci, Inst Automat, Beijing, Peoples R China
2.Univ Chinese Acad Sci, Beijing, Peoples R China
3.China Foreign Affairs Univ, Beijing, Peoples R China
4.Henan Polytech Univ, Sch Comp Sci & Technol, Jiaozuo 454000, Henan, Peoples R China
5.Univ Sci & Technol Beijing, Sch Automat & Elect Engn, Beijing 100083, Peoples R China
6.Tsinghua Univ, Beijing, Peoples R China
7.Natl Lab Pattern Recognit, 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.

入库方式： OAI收割

来源：自动化研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。