K-means based double-bit quantization for hashing

Hashing function is an efficient way for nearest neighbor search in massive dataset because of low storage cost and low computational cost. However, it is NP hard problem to transform data points from the original space into a new hypercube space directly. Typically, the most of hashing methods choose a two-stage strategy. In the first stage, dimension reduction methods are used to project original data into desired dimensionality with real values. Then in the second stage, the real values are simply quantized into binary codes by thresholding for the most of existing methods. Although there is double-bit quantization (DBQ) strategy to improve quantization results. The existing solutions assume that the input data subject to gaussian distribution. In this paper, we propose a novel approach based on DBQ strategy, which can efficiently handle the situation under non-Gaussian distribution input. In the experiments, we demonstrate that our method is an efficient alternative to other methods based on DBQ strategy.