Density Sensitive Hashing
- 23 October 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Cybernetics
- Vol. 44 (8), 1362-1371
- https://doi.org/10.1109/tcyb.2013.2283497
Abstract
Nearest neighbor search is a fundamental problem in various research fields like machine learning, data mining and pattern recognition. Recently, hashing-based approaches, for example, locality sensitive hashing (LSH), are proved to be effective for scalable high dimensional nearest neighbor search. Many hashing algorithms found their theoretic root in random projection. Since these algorithms generate the hash tables (projections) randomly, a large number of hash tables (i.e., long codewords) are required in order to achieve both high precision and recall. To address this limitation, we propose a novel hashing algorithm called density sensitive hashing (DSH) in this paper. DSH can be regarded as an extension of LSH. By exploring the geometric structure of the data, DSH avoids the purely random projections selection and uses those projective functions which best agree with the distribution of the data. Extensive experimental results on real-world data sets have shown that the proposed method achieves better performance compared to the state-of-the-art hashing approaches.Keywords
Funding Information
- National Basic Research Program of China (973 Program) (2013CB336500)
- National Nature Science Foundation of China (61222207, 91120302)
This publication has 27 references indexed in Scilit:
- Compressed HashingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Weakly-supervised hashing in kernel spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Locality sensitive hashing: A comparison of hash function types and querying mechanismsPattern Recognition Letters, 2010
- Kernelized locality-sensitive hashing for scalable image searchPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- A posteriori multi-probe locality sensitive hashingPublished by Association for Computing Machinery (ACM) ,2008
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensionsCommunications of the ACM, 2008
- Entropy based nearest neighbor search in high dimensionsPublished by Association for Computing Machinery (ACM) ,2006
- The Priority R-treePublished by Association for Computing Machinery (ACM) ,2004
- Voronoi-Based K Nearest Neighbor Search for Spatial Network DatabasesPublished by Elsevier BV ,2004
- Extensions of Lipschitz mappings into a Hilbert spaceContemporary Mathematics, 1984