The Idea of Densification

Traditional Minwise Hashing is slow. Applications require computing thousands of minhashes for dimensionality reduction, compression, etc. Computing MinHashes needs thousands of passes over the data which is unnecessarily expensive. We show single pass and constant time minwiseh hashing algorithm which can be thousands of time faster than the fastest MinHash code. We use densification for fast minwise hashing over sparse data.

Red-Green Sampling

For weighted minwise hashing it is possible to construct a novel red-green map which can mimic the minwise sampling distribution requiring only 1/sparsity number of random numbers. We obtain a tremendous (60000x) speedup on many real tasks.