Near-isometric Binary Hashing For Large-scale Datasets

Aghazadeh Amirali, Lan Andrew, Shrivastava Anshumali, Baraniuk Richard. Arxiv 2016

[Paper]    
ARXIV Independent

We develop a scalable algorithm to learn binary hash codes for indexing large-scale datasets. Near-isometric binary hashing (NIBH) is a data-dependent hashing scheme that quantizes the output of a learned low-dimensional embedding to obtain a binary hash code. In contrast to conventional hashing schemes, which typically rely on an $\ell ₂$-norm (i.e., average distortion) minimization, NIBH is based on a ${\ell }_{\mathrm{\infty }}$-norm (i.e., worst-case distortion) minimization that provides several benefits, including superior distance, ranking, and near-neighbor preservation performance. We develop a practical and efficient algorithm for NIBH based on column generation that scales well to large datasets. A range of experimental evaluations demonstrate the superiority of NIBH over ten state-of-the-art binary hashing schemes.

Similar Work

• Structured Learning Of Binary Codes With Column Generation
• A Quantized Johnson Lindenstrauss Lemma The Finding Of Buffons Needle
• Supervised Hashing With End-to-end Binary Deep Neural Network
• Learning Hash Functions Using Column Generation