On Densification for Minwise Hashing

Tung Mai, Anup Rao, Matt Kapilevich, Ryan A. Rossi, Yasin Abbasi-Yadkori, Ritwik SinhaUAI 2019 · OpenReview

Abstract

One Permutation Hashing (OPH) is a significantly more efficient alternative to the popular minwise hashing. To produce a sketch of size $k$, OPH requires just one hash function whereas the classical minwise hashing requires $k$ independent hash functions. However, OPH faces the "empty bin" problem in sparse datasets, which necessitates a process called "densification" to maintain the Locality Sensitive Hashing (LSH) property. This paper introduces a significantly faster and more accurate way to perform densification. By shifting from a "pull" to a "push" hashing strategy, the authors reduced the computational complexity from $O(k^2)$ to $O(k \log k)$ while simultaneously achieving lower variance (better accuracy) than previous state-of-the-art methods.

Introduction

In large-scale data processing, comparing massive sets (e.g., documents or user logs) is a fundamental but computationally expensive task. Minwise Hashing (Minhash) is the standard technique for estimating Jaccard Similarity, a measure of overlap between two sets. While effective, traditional Minhash requires $k$ different hash functions to create a sketch of size $k$, which becomes a bottleneck as $k$ grows.

One Permutation Hashing (OPH) addresses this by using a single hash function and partitioning the space into $k$ bins. However, for sparse data, many bins may remain empty. These empty bins break the LSH property, rendering the sketches ineffective for fast indexing. "Densification" is the necessary step of filling these empty bins by copying values from non-empty ones. Previous densification routines were either mathematically suboptimal (high variance) or computationally inefficient, often exhibiting quadratic time complexity relative to the sketch size $k$.

Theoretical Framework: The Consistency Condition

The authors provide a theoretical unification of densification methods by proving a "necessary and sufficient" condition for a densification routine to be valid. They define Consistent Densification, demonstrating that as long as the rule for filling an empty bin follows a "consistent sampling" process, the resulting sketch preserves the crucial LSH property. This framework explains why previous methods worked and provides a blueprint for designing superior algorithms.

The $h^o$ Algorithm: From "Pull" to "Push"

The core algorithmic contribution is the Faster Densification algorithm ($h^o$). Previous methods employed a "pull" approach: each empty bin would iteratively search for a non-empty neighbor to copy from. In sparse data, this search is inefficient.

The proposed $h^o$ method reverses this logic into a "push" approach:

  1. Iterate through the non-empty bins.
  2. Use a family of hash functions to "map" (push) these non-empty values into the empty slots.
  3. By broadcasting values from non-empty bins to empty ones, the algorithm fills the gaps much faster—achieving an expected time complexity of $O(k \log k)$.

Experimental Evaluation

The algorithm was evaluated on three large-scale, sparse text datasets: RCV1 (newswire articles), URL (malicious/benign URLs), and News20 (newsgroup documents).

Performance and Scaling

The "push" strategy leads to dramatic speedups. For a sketch size of $k = 10,000$, the $h^o$ method was 6x to 19x faster than the previous state-of-the-art ($h^*$). Crucially, while $h^*$ exhibits quadratic runtime growth, $h^o$ scales nearly linearly with the number of hashes.

Average runtime comparison. The proposed $h^o$ method (blue) scales nearly linearly with the number of hashes, whereas the previous state-of-the-art $h^*$ (orange) exhibits quadratic growth.

Accuracy and Variance

Beyond speed, the $h^o$ algorithm reduces estimation error. By distributing values more evenly across empty bins, it minimizes the chance of accidental replications that lead to higher variance. Experimental results show that $h^o$ consistently achieves lower Mean Squared Error (MSE) than prior methods across various Jaccard similarity levels.

Mean Squared Error (MSE) across various Jaccard similarity levels (J). The proposed $h^o$ method (blue) consistently outperforms previous densification techniques as the number of hashes increases.

Conclusion

This work advances the state of the art in OPH by providing both a rigorous theoretical foundation for densification and a highly efficient "push-based" algorithm. The $h^o$ method offers a rare "win-win" in algorithm design: it is significantly faster and more accurate than its predecessors, making high-precision Jaccard similarity estimation practical for even larger datasets.

Summary updated

Abstract

One Permutation Hashing (OPH) is a significantly more efficient alternative to the popular minwise hashing. To produce a sketch of size $k$, OPH requires just one hash function whereas the classica...
BibTeX
@inproceedings{mai2019densification,
  author = {Tung Mai and Anup Rao and Matt Kapilevich and Ryan A. Rossi and Yasin Abbasi-Yadkori and Ritwik Sinha},
  title = {{On Densification for Minwise Hashing}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=SZVW6BeQOJ5},
}
Figure