Accelerated Manhattan hashing via bit-remapping with location information

详细信息    查看全文

• 作者：Wenshuo Chen ; Guiguang Ding ; Zijia Lin ; Jisheng Pei
• 关键词：Accelerated Manhattan hashing ; Bit ; remapping ; Multiple ; bit quantization ; Manhattan distance
• 刊名：Multimedia Tools and Applications
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：76
• 期：2
• 页码：2441-2466
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Multimedia Information Systems; Computer Communication Networks; Data Structures, Cryptology and Information Theory; Special Purpose and Application-Based Systems;
• 出版者：Springer US
• ISSN：1573-7721
• 卷排序：76

文摘

Hashing is a binary-code encoding method which tries to preserve the neighborhood structures in the original feature space, in order to realize efficient approximate nearest neighbor search in large-scale databases. Existing hashing methods usually adopt a two-stage strategy (projection stage and quantization stage) to encode data points, and threshold-based single-bit quantization (SBQ) is used to binarize each projected dimension into 0 or 1. Data similarity between hash codes is measured by their Hamming distance. However, SBQ may destroy the original neighborhood structures by quantizing neighboring points near threshold into different binary values. Double-bit quantization (DBQ) and its derivative, Manhattan hashing, have been proposed to fix this problem. Experimental results showed that Manhattan hashing outperformed state-of-the-art methods in terms of effectiveness, but lost the advantage of efficiency because it used decimal arithmetic instead of fast bitwise operations for similarity measurement between hash codes. In this paper, we propose an accelerated strategy of Manhattan hashing by making full use of bitwise operations. Our main contributions are: 1) a new encoding method which assigns location information to each binary digit is proposed to avoid the time-consuming decimal arithmetic; 2) a novel hash code distance measurement that accelerates the calculation of Manhattan distance is proposed to improve query efficiency. Extensive experiments on three benchmark datasets show that our approach improves the speed of data querying on 2-bit, 3-bit and 4-bit quantized hash codes by at least one order of magnitude on average, without any precision loss.