Compressed hashing

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 perfor-mance, 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 a sparse coding scheme, based on the approximation the-ory of integral operator, that generate sparse represen-tation for high dimensional vectors. We then project sparse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the the-oretical analysis and the empirical studies on two large data sets show that the proposed approach is more ef-fective than the state-of-the-art hashing algorithms. 1