Multi‐bit quantisation for similarity‐preserving hashing

Abstract

As a promising alternative to traditional search techniques, hashing‐based approximate nearest neighbour search provides an applicable solution for big data. Most existing efforts are devoted to finding better projections to preserve the neighbouring structure of original data points in Hamming space, but ignore the quantisation procedure which may lead to the breakdown of the neighbouring structure maintained in the projection stage. To address this issue, the authors propose a novel multi‐bit quantisation (MBQ) method using a Matthews correlation coefficient (MCC) term and a regularisation term. The authors' method utilises the neighbouring relationship and the distribution information of original data points instead of the projection dimension usually used in the previous MBQ methods to adaptively learn optimal quantisation thresholds, and allocates multiple bits per projection dimension in terms of the learned thresholds. Experiments on two typical image data sets demonstrate that the proposed method effectively preserves the similarity between data points in the original feature space and outperforms state‐of‐the‐art quantisation methods.

Keywords

• multibit quantisation
• similarity-preserving hashing
• hashing-based approximate nearest neighbour search
• Big Data
• Hamming space
• MBQ method