# Optimal Densification for Fast and Accurate Minwise Hashing

arXiv: https://arxiv.org/abs/1703.04664 · HTML: https://mlsanity.com/paper/1703.04664/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2017.

## Built on by (most cited first, 7 of 7)

- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with Circulant Permutations](https://mlsanity.com/paper/2111.09544/) (2021)
- [A Fast Randomized Algorithm for Massive Text Normalization](https://mlsanity.com/paper/2110.03024/) (2021)
- [Fast Gumbel-Max Sketch and its Applications](https://mlsanity.com/paper/2302.05176/) (2023)
- [Fast Locality Sensitive Hashing with Theoretical Guarantee](https://mlsanity.com/paper/2309.15479/) (2023)
- [Improving LSH via Tensorized Random Projection](https://mlsanity.com/paper/2402.07189/) (2024)
- [Understanding Circulant Permutation to Extend the CMinHash Estimator](https://mlsanity.com/paper/2610.18551/) (2026)

## Abstract (arXiv)

Minwise hashing is a fundamental and one of the most successful hashing algorithm in the literature. Recent advances based on the idea of densification~citeProc:OneHashLSHICML14,Proc:ShrivastavaUAI14 have shown that it is possible to compute k minwise hashes, of a vector with d nonzeros, in mere (d + k) computations, a significant improvement over the classical O(dk). These advances have led to an algorithmic improvement in the query complexity of traditional indexing algorithms based on minwise hashing. Unfortunately, the variance of the current densification techniques is unnecessarily high, which leads to significantly poor accuracy compared to vanilla minwise hashing, especially when the data is sparse. In this paper, we provide a novel densification scheme which relies on carefully tailored 2-universal hashes. We show that the proposed scheme is variance-optimal, and without losing the runtime efficiency, it is significantly more accurate than existing densification techniques. As a result, we obtain a significantly efficient hashing scheme which has the same variance and collision probability as minwise hashing. Experimental evaluations on real sparse and high-dimensional datasets validate our claims. We believe that given the significant advantages, our method will replace minwise hashing implementations in practice.