A distance-computation-free search scheme for binary code databases

Song, Jingkuan, Shen, Heng Tao, Wang, Jianfeng, Huang, Zi, Sebe, Nicu and Wang, Jingdong (2016) A distance-computation-free search scheme for binary code databases. IEEE Transactions on Multimedia, 18 3: 484-495. doi:10.1109/TMM.2016.2515990

Author Song, Jingkuan
Shen, Heng Tao
Wang, Jianfeng
Huang, Zi
Sebe, Nicu
Wang, Jingdong
Title A distance-computation-free search scheme for binary code databases
Journal name IEEE Transactions on Multimedia   Check publisher's open access policy
ISSN 1520-9210
Publication date 2016-03-01
Sub-type Article (original research)
DOI 10.1109/TMM.2016.2515990
Volume 18
Issue 3
Start page 484
End page 495
Total pages 12
Place of publication Piscataway, United States
Publisher Institute of Electrical and Electronics Engineers
Language eng
Formatted abstract
Recently, binary codes have been widely used in many multimedia applications to approximate high-dimensional multimedia features for practical similarity search due to the highly compact data representation and efficient distance computation. While the majority of the hashing methods aim at learning more accurate hash codes, only a few of them focus on indexing methods to accelerate the search for binary code databases. Among these indexing methods, most of them suffer from extremely high memory cost or extensive Hamming distance computations. In this paper, we propose a new Hamming distance search scheme for large scale binary code databases, which is free of Hamming distance computations to return the exact results. Without the necessity to compare database binary codes with queries, the search performance can be improved and databases can be externally maintained. More specifically, we adopt the inverted multi-index data structure to index binary codes. Importantly, the Hamming distance information embedded in the structure is utilized in the designed search scheme such that the verification of exact results no longer relies on Hamming distance computations. As a step further, we optimize the performance of the inverted multi-index structure by taking the code distributions among different bits into account for index construction. Empirical results on large-scale binary code databases demonstrate the superiority of our method over existing approaches in terms of both memory usage and search efficiency.
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: HERDC Pre-Audit
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 7 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 25 Jan 2016, 20:58:08 EST by Dr Heng Tao Shen on behalf of School of Information Technol and Elec Engineering