Random Maximum Margin Hashing

Alexis Joly 1, 2, * Olivier Buisson 3
* Corresponding author
2 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Following the success of hashing methods for multidimensional indexing, more and more works are interested in embedding visual feature space in compact hash codes. Such approaches are not an alternative to using index structures but a complementary way to reduce both the memory usage and the distance computation cost. Several data dependent hash functions have notably been proposed to closely fit data distribution and provide better selectivity than usual random projections such as LSH. However, improvements occur only for relatively small hash code sizes up to 64 or 128 bits. As discussed in the paper, this is mainly due to the lack of independence between the produced hash functions. We introduce a new hash function family that attempts to solve this issue in any kernel space. Rather than boosting the collision probability of close points, our method focus on data scattering. By training purely random splits of the data, regardless the closeness of the training samples, it is indeed possible to generate consistently more independent hash functions. On the other side, the use of large margin classifiers allows to maintain good generalization performances. Experiments show that our new Random Maximum Margin Hashing scheme (RMMH) outperforms four state-of-the-art hashing methods, notably in kernel spaces.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00642178
Contributor : Alexis Joly <>
Submitted on : Thursday, November 17, 2011 - 3:07:18 PM
Last modification on : Thursday, October 10, 2019 - 11:46:03 AM
Long-term archiving on: Sunday, December 4, 2016 - 6:26:10 PM

File

rmmh-cvpr-certified-IEEE-eXpre...
Files produced by the author(s)

Identifiers

Collections

Citation

Alexis Joly, Olivier Buisson. Random Maximum Margin Hashing. CVPR'11 - IEEE Computer Vision and Pattern Recognition, Jun 2011, Colorado springs, United States. pp.873-880, ⟨10.1109/CVPR.2011.5995709⟩. ⟨hal-00642178⟩

Share

Metrics

Record views

626

Files downloads

1522