A Distance-Computation-Free Search Scheme for Binary Code Databases
- 8 January 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Multimedia
- Vol. 18 (3) , 484-495
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.Keywords
This publication has 30 references indexed in Scilit:
- A Prior-Free Weighting Scheme for Binary Code RankingIEEE Transactions on Multimedia, 2014
- HmSearch2013
- Effective Multiple Feature Hashing for Large-Scale Near-Duplicate Video RetrievalIEEE Transactions on Multimedia, 2013
- Inter-media hashing for large-scale retrieval from heterogeneous data sources2013
- K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes2013
- Multiple feature hashing for real-time large scale near-duplicate video retrieval2011
- Searching in one billion vectors: Re-rank with source coding2011
- Self-taught hashing for fast similarity search2010
- Semi-supervised hashing for scalable image retrieval2010
- 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene RecognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008