Hashing Algorithms For Large-scale Learning

Ping Li, Anshumali Shrivastava, Joshua Moore, Arnd König. Neural Information Processing Systems 2011

[Paper]    
NEURIPS Supervised

Minwise hashing is a standard technique in the context of search for efficiently computing set similarities. The recent development of b-bit minwise hashing provides a substantial improvement by storing only the lowest b bits of each hashed value. In this paper, we demonstrate that b-bit minwise hashing can be naturally integrated with linear learning algorithms such as linear SVM and logistic regression, to solve large-scale and high-dimensional statistical learning tasks, especially when the data do not fit in memory. We compare $b$-bit minwise hashing with the Count-Min (CM) and Vowpal Wabbit (VW) algorithms, which have essentially the same variances as random projections. Our theoretical and empirical comparisons illustrate that b-bit minwise hashing is significantly more accurate (at the same storage cost) than VW (and random projections) for binary data.

Similar Work

• Training Logistic Regression And SVM On 200GB Data Using B-bit Minwise Hashing And Comparisons With Vowpal Wabbit (VW)
• Accurate Estimators For Improving Minwise Hashing And B-bit Minwise Hashing
• B-bit Minwise Hashing For Large-scale Linear SVM
• B-bit Minwise Hashing For Estimating Three-way Similarities