A General Framework for Linear Distance Preserving Hashing.

Abstract

Binary hashing approaches the approximate nearest neighbor search problem by transferring the data to Hamming space with explicit or implicit distance preserving constraint. With compact data representation, binary hashing identifies the approximate nearest neighbors via very efficient Hamming distance computation. In this paper, we propose a generic hashing framework with a new linear pairwise distance preserving objective and pointwise constraint. In our framework, the direct distance preserving objective aims to keep the linear relationship between the Euclidean distance and the Hamming distance of data points. On the other hand, to impose the pointwise constraint, we instantiate the framework from three different perspectives with pseudo-supervised, unsupervised, and supervised clues and obtain three different hashing methods. The first one is a pseudo-supervised hashing method, which adopts a certain existing unsupervised hashing method to generate binary codes as pseudo-supervised information. For the second one, we get an unsupervised hashing method by considering the quantization loss. The third one, as a supervised hashing method, learns the hash functions in a two-step paradigm. Furthermore, we improve the above-mentioned framework by constraining the global scope of the proposed linear distance preserving objective to a local range. We validate our framework on four large-scale benchmark data sets. The experiments demonstrate that our pseudo-supervised method achieves consistent improvement over the state-of-the-art unsupervised hashing methods, while our unsupervised and supervised methods achieve promising performance compared with the state-of-the-art algorithms.