  Fast nearest neighbor searching is becoming an increasingly important tool in
solving many large-scale problems. Recently a number of approaches to learning
data-dependent hash functions have been developed. In this work, we propose a
column generation based method for learning data-dependent hash functions on
the basis of proximity comparison information. Given a set of triplets that
encode the pairwise proximity comparison information, our method learns hash
functions that preserve the relative comparison relationships in the data as
well as possible within the large-margin learning framework. The learning
procedure is implemented using column generation and hence is named CGHash. At
each iteration of the column generation procedure, the best hash function is
selected. Unlike most other hashing methods, our method generalizes to new data
points naturally; and has a training objective which is convex, thus ensuring
that the global optimum can be identified. Experiments demonstrate that the
proposed method learns compact binary codes and that its retrieval performance
compares favorably with state-of-the-art methods when tested on a few benchmark
datasets.
