Fast approximate matching of binary codes with distinctive bits

doi:10.1007/s11704-015-4192-0

	Fast approximate matching of binary codes with distinctive bits
	Yan, Chenggang Clarence 2,3; Xie, Hongtao 1; Zhang, Bing 4; Ma, Yanping 5; Dai, Qiong 1; Liu, Yizhi 6
	2015-10-01
发表期刊	FRONTIERS OF COMPUTER SCIENCE
ISSN	2095-2228
卷号	9 期号:5 页码:741-750
摘要	Although the distance between binary codes can be computed fast in Hamming space, linear search is not practical for large scale datasets. Therefore attention has been paid to the efficiency of performing approximate nearest neighbor search, in which hierarchical clustering trees (HCT) are widely used. However, HCT select cluster centers randomly and build indexes with the entire binary code, this degrades search performance. In this paper, we first propose a new clustering algorithm, which chooses cluster centers on the basis of relative distances and uses a more homogeneous partition of the dataset than HCT has to build the hierarchical clustering trees. Then, we present an algorithm to compress binary codes by extracting distinctive bits according to the standard deviation of each bit. Consequently, a new index is proposed using compressed binary codes based on hierarchical decomposition of binary spaces. Experiments conducted on reference datasets and a dataset of one billion binary codes demonstrate the effectiveness and efficiency of our method.
关键词	binary codes approximate nearest neighbor search hierarchical clustering index
DOI	10.1007/s11704-015-4192-0
收录类别	SCI
语种	英语
资助项目	National High Technology Research and Development Program[2012AA012502] ; National Nature Science Foundation of China[61303171] ; National Nature Science Foundation of China[61472203] ; Chinese Academy of Sciences[XDA06031000] ; Hunan Provincial Natural Science Foundation of China[2015JJ2056] ; Hunan Provincial University Innovation Platform Open Fund Project of China[14K037] ; China Postdoctoral Science Foundation
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:000361611300008
出版者	HIGHER EDUCATION PRESS
引用统计	被引频次：6[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9377
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Hongtao
作者单位	1.Chinese Acad Sci, Natl Engn Lab Informat Secur Technol, Inst Informat Engn, Beijing 100093, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 3.Tsinghua Univ, Dept Automat, Beijing 100083, Peoples R China 4.Beijing Inst Technol, Sch Phys, Beijing 100081, Peoples R China 5.Ocean Univ China, Sch Informat Sci & Engn, Qingdao 266100, Peoples R China 6.Hunan Univ Sci & Technol, Sch Comp Sci & Engn, Xiangtan 411201, Peoples R China
推荐引用方式 GB/T 7714	Yan, Chenggang Clarence,Xie, Hongtao,Zhang, Bing,et al. Fast approximate matching of binary codes with distinctive bits[J]. FRONTIERS OF COMPUTER SCIENCE,2015,9(5):741-750.
APA	Yan, Chenggang Clarence,Xie, Hongtao,Zhang, Bing,Ma, Yanping,Dai, Qiong,&Liu, Yizhi.(2015).Fast approximate matching of binary codes with distinctive bits.FRONTIERS OF COMPUTER SCIENCE,9(5),741-750.
MLA	Yan, Chenggang Clarence,et al."Fast approximate matching of binary codes with distinctive bits".FRONTIERS OF COMPUTER SCIENCE 9.5(2015):741-750.