Complementary Binary Quantization for Joint Multiple Indexing

Complementary Binary Quantization for Joint Multiple Indexing

Qiang Fu, Xu Han, Xianglong Liu, Jingkuan Song, Cheng Deng

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 2114-2120. https://doi.org/10.24963/ijcai.2018/292

Building multiple hash tables has been proven a successful technique for indexing massive databases, which can guarantee a desired level of overall performance. However, existing hash based multi-indexing methods suffer from the heavy redundancy, without strong table complementarity and effective hash code learning. To address the problems, this paper proposes a complementary binary quantization (CBQ) method to jointly learning multiple hash tables. It exploits the power of incomplete binary coding based on prototypes to align the original space and the Hamming space, and further utilizes the nature of multi-indexing search to jointly reduce the quantization loss based on the prototype based hash function. Our alternating optimization adaptively discovers the complementary prototype sets and the corresponding code sets of a varying size in an efficient way, which together robustly approximate the data relations. Our method can be naturally generalized to the product space for long hash codes. Extensive experiments carried out on two popular large-scale tasks including Euclidean and semantic nearest neighbor search demonstrate that the proposed CBQ method enjoys the strong table complementarity and significantly outperforms the state-of-the-art, with up to 57.76\% performance gains relatively.
Keywords:
Machine Learning: Unsupervised Learning
Computer Vision: Recognition: Detection, Categorization, Indexing, Matching, Retrieval, Semantic Interpretation
Heuristic Search and Game Playing: Heuristic Search and Machine Learning
Computer Vision: Computer Vision