b-Bit Minwise Hashing for Large-Scale Learning

Summary

It is demonstrated 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.

Keywords

Hash function, Computer science, Context (archaeology), Algorithm, Dynamic perfect hashing

References

Accurate Estimators for Improving Minwise Hashing and b-Bit Minwise HashingPing Li, Konig, Christian — 2011
b-Bit Minwise Hashing in Practice: Large-Scale Batch and Online Learning and Using GPUs for Fast Preprocessing with Simple Hash FunctionsPing Li, Anshumali Shrivastava, Arnd Christian König — 2012
Finding text reuse on the webMichael Bendersky, W. Bruce Croft — 2009
On compressing social networksFlavio Chierichetti, Ravi Kumar, Silvio Lattanzi — 2009
Efficient detection of large-scale redundancy in enterprise file systemsGeorge Forman, Kave Eshghi, Jaap Suermondt — 2009
Training linear SVMs in linear timeThorsten Joachims — 2006
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High DimensionsAlexandr Andoni, Piotr Indyk — 2006
Extraction and classification of dense implicit communities in the Web graphYon Dourisboure, Filippo Geraci, Marco Pellegrini — 2009
Very sparse random projectionsPing Li, Trevor Hastie, Kenneth Church — 2006
Feature hashing for large scale multitask learningKilian Q. Weinberger, Anirban Dasgupta, John Langford — 2009
Theory and applications of b-bit minwise hashingPing Li, Arnd Christian König — 2011
LIBLINEAR: A Library for Large Linear ClassificationRong-En Fan, Kai‐Wei Chang, Cho‐Jui Hsieh — 2008
b-Bit Minwise Hashing for Estimating Three-Way SimilaritiesPing Li, Arnd Christian König, Wenhao Gui — 2010
On the resemblance and containment of documentsArndt Bröder — 1997
b-Bit minwise hashingLi Ping, Christian König — 2009
Detecting near-duplicates for web crawlingGurmeet Singh Manku, Arvind Kumar Jain, Anish Das Sarma — 2007
An axiomatic approach for result diversificationSreenivas Gollapudi, Aneesh Sharma — 2009
Syntactic Clustering of the WebAndrei Broder, S. Glassman, Mark S. Manasse — 1997
A dual coordinate descent method for large-scale linear SVMCho‐Jui Hsieh, Kai‐Wei Chang, Chih‐Jen Lin — 2008
A large‐scale study of the evolution of Web pagesDennis Fetterly, Mark S. Manasse, Marc Najork — 2003

Cited by

Connected bit minwise hashing for large-scale linear SVMJingjing Tang, Yingjie Tian, Dalian Liu — 2015
A Systematic Review on Minwise Hashing AlgorithmsJingjing Tang, Yingjie Tian — 2016
HashEclat: an efficient frequent itemset algorithmChunkai Zhang, Panbo Tian, Xudong Zhang — 2019
Improved Consistent Weighted Sampling RevisitedWei Wu, Bin Li, Ling Chen — 2017

Related papers

Sparse multinomial logistic regression: fast algorithms and generalization boundsBalaji Krishnapuram, Lawrence Carin, Mário A. T. Figueiredo — 2005
Maximum Entropy Based Associative Regression for Sparse DatasetsAneesh Sreevallabh Chivukula, Vikram Pudi — 2014
Semi Supervised Logistic RegressionMassih-Reza Amini, Patrick Gallinari — 2002
Efficient Online Learning for Large-Scale Sparse Kernel Logistic RegressionLijun Zhang, Rong Jin, Chun Chen — 2012
Sparse Kernel Logistic Regression using Incremental Feature Selection for Text-Independent Speaker IdentificationMarcel Katz, Martin Schafföner, Edin Andelic — 2006
Unsupervised Supervised Learning I: Estimating Classification and Regression Errors without LabelsPınar Dönmez, Guy Lebanon, Krishnakumar Balasubramanian — 2010
Estimating expected error rates of random forest classifiers: A comparison of cross-validation and bootstrapMilica Ljumovic, Michael Klar — 2015