Compressed Hashing
- 1 June 2013
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 446-451
- https://doi.org/10.1109/cvpr.2013.64
Abstract
Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. A common problem shared by many existing hashing methods is that in order to achieve a satisfied performance, a large number of hash tables (i.e., long code-words) are required. To address this challenge, in this paper we propose a novel approach called Compressed Hashing by exploring the techniques of sparse coding and compressed sensing. In particular, we introduce as parse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. We then project s-parse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the theoretical analysis and the empirical studies on two large data sets show that the proposed approach is more effective than the state-of-the-art hashing algorithms.Keywords
This publication has 13 references indexed in Scilit:
- Random maximum margin hashingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Geometry on Probability SpacesConstructive Approximation, 2009
- Kernelized locality-sensitive hashing for scalable image searchPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathematique, 2008
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensionsCommunications of the ACM, 2008
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Entropy based nearest neighbor search in high dimensionsPublished by Association for Computing Machinery (ACM) ,2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Locality-sensitive hashing scheme based on p-stable distributionsPublished by Association for Computing Machinery (ACM) ,2004
- Extensions of Lipschitz mappings into a Hilbert spaceContemporary Mathematics, 1984