Maximum Variance Hashing via Column Generation

Lei Luo, Chao Zhang, Yongrui Qin, Chunyuan Zhang

Research output: Contribution to journalArticle

Abstract

With the explosive growth of the data volume in modern applications such as web search and multimedia retrieval, hashing is becoming increasingly important for efficient nearest neighbor (similar item) search. Recently, a number of data-dependent methods have been developed, reflecting the great potential of learning for hashing. Inspired by the classic nonlinear dimensionality reduction algorithm - maximum variance unfolding, we propose a novel unsupervised hashing method, named maximum variance hashing, in this work. The idea is to maximize the total variance of the hash codes while preserving the local structure of the training data. To solve the derived optimization problem, we propose a column generation algorithm, which directly learns the binary-valued hash functions. We then extend it using anchor graphs to reduce the computational cost. Experiments on large-scale image datasets demonstrate that the proposed method outperforms state-of-the-art hashing methods in many cases.

Original languageEnglish
Article number379718
Number of pages10
JournalMathematical Problems in Engineering
Volume2013
Early online date15 May 2013
DOIs
Publication statusPublished - 14 Jun 2013
Externally publishedYes

Fingerprint Dive into the research topics of 'Maximum Variance Hashing via Column Generation'. Together they form a unique fingerprint.

  • Cite this