Random maximum margin hashing
- 1 June 2011
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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.Keywords
This publication has 16 references indexed in Scilit:
- SPEC hashing: Similarity preserving algorithm for entropy-based codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Locality sensitive hashing: A comparison of hash function types and querying mechanismsPattern Recognition Letters, 2010
- Product Quantization for Nearest Neighbor SearchIeee Transactions On Pattern Analysis and Machine Intelligence, 2010
- Z-grid-based probabilistic retrieval for scaling up content-based copy detectionPublished by Association for Computing Machinery (ACM) ,2007
- Restricted Boltzmann machines for collaborative filteringPublished by Association for Computing Machinery (ACM) ,2007
- Feature statistical retrieval applied to content-based copy identificationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Generalized histogram intersection kernel for image recognitionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Locality-sensitive hashing scheme based on p-stable distributionsPublished by Association for Computing Machinery (ACM) ,2004
- Similarity estimation techniques from rounding algorithmsPublished by Association for Computing Machinery (ACM) ,2002
- Object recognition from local scale-invariant featuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999