BitHash: An efficient bitwise Locality Sensitive Hashing method with applications
详细信息 查看全文
- 作者：Wenhao Zhang ; Jianqiu Ji ; Jun Zhu ; Jianmin Li ; Hua Xu ; xuhua@mail.tsinghua.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Bo Zhang
- 关键词：Locality Sensitive Hashing ; BitHash ; Near-duplicate detection ; Machine learning ; Sentiment analysis ; Storage efficiency
- 刊名：Knowledge-Based Systems
- 出版年：2016
- 出版时间：1 April 2016
- 年：2016
- 卷：97
- 期：Complete
- 页码：40-47
- 全文大小：1201 K
文摘
Locality Sensitive Hashing has been applied to detecting near-duplicate images, videos and web documents. In this paper we present a Bitwise Locality Sensitive method by using only one bit per hash value (BitHash), the storage space for storing hash values is significantly reduced, and the estimator can be computed much faster. The method provides an unbiased estimate of pairwise Jaccard similarity, and the estimator is a linear function of Hamming distance, which is very simple. We rigorously analyze the variance of One-Bit Min-Hash (BitHash), showing that for high Jaccard similarity. BitHash may provide accurate estimation, and as the pairwise Jaccard similarity increases, the variance ratio of BitHash over the original min-hash decreases. Furthermore, BitHash compresses each data sample into a compact binary hash code while preserving the pairwise similarity of the original data. The binary code can be used as a compressed and informative representation in replacement of the original data for subsequent processing. For example, it can be naturally integrated with a classifier like SVM. We apply BitHash to two typical applications, near-duplicate image detection and sentiment analysis. Experiments on real user’s photo collection and a popular sentiment analysis data set show that, the classification accuracy of our proposed method for two applications could approach the state-of-the-art method, while BitHash only requires a significantly smaller storage space.