RHash: Robust Hashing via ℓ-norm distortion

Amirali Aghazadeh, Andrew Lan, Anshumali Shrivastava, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Hashing is an important tool in large-scale machine learning. Unfortunately, current data-dependent hashing algorithms are not robust to small perturbations of the data points, which degrades the performance of nearest neighbor (NN) search. The culprit is the minimization of the ℓ2-norm, average distortion among pairs of points to find the hash function. Inspired by recent progress in robust optimization, we develop a novel hashing algorithm, dubbed RHash, that instead minimizes the ℓ-norm, worst-case distortion among pairs of points. We develop practical and efficient implementations of RHash that couple the alternating direction method of multipliers (ADMM) framework with column generation to scale well to large datasets. A range of experimental evaluations demonstrate the superiority of RHash over ten state-of-the-art binary hashing schemes. In particular, we show that RHash achieves the same retrieval performance as the state-of-the-art algorithms in terms of average precision while using up to 60% fewer bits.

Original languageEnglish (US)
Title of host publication26th International Joint Conference on Artificial Intelligence, IJCAI 2017
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1386-1394
Number of pages9
ISBN (Electronic)9780999241103
StatePublished - 2017
Event26th International Joint Conference on Artificial Intelligence, IJCAI 2017 - Melbourne, Australia
Duration: Aug 19 2017Aug 25 2017

Other

Other26th International Joint Conference on Artificial Intelligence, IJCAI 2017
CountryAustralia
CityMelbourne
Period8/19/178/25/17

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'RHash: Robust Hashing via ℓ<sub>∞</sub>-norm distortion'. Together they form a unique fingerprint.

Cite this