BagMinHash - Minwise Hashing Algorithm for Weighted Sets

Otmar ErtlKDD 2018 · DOI · arXiv

Abstract

Estimating Jaccard similarity for weighted sets is a critical task in large-scale data analysis. Traditional methods like Improved Consistent Weighted Sampling (ICWS) suffer from $O(mn)$ complexity, where $m$ is the signature size and $n$ is the number of elements. We present BagMinHash, an algorithm that leverages Poisson processes and early termination strategies to achieve orders-of-magnitude speedups. Unlike several recent "fast" alternatives that introduce bias, BagMinHash maintains statistical independence and theoretical accuracy.

Introduction

In data science, comparing the similarity of two objects is fundamental. For sets, Jaccard similarity is the standard metric. Minwise hashing allows for "sketching" these sets into small signatures for fast estimation. However, weighted sets (e.g., word frequencies) present a challenge. The standard ICWS algorithm is prohibitively slow for large datasets ($n$) and large signature sizes ($m$). While recent works have attempted to optimize this, many suffer from theoretical flaws leading to biased results.

Methods

BagMinHash reimagines minwise hashing through the lens of Poisson processes. Instead of the "compute everything" approach, it generates potential minimum hash values in ascending order.

Technical Innovations

  • Discretization: By assuming discrete weights at standard floating-point precision, the algorithm achieves negligible error compared to statistical variance.
  • Poisson Process Interpretation: The core treats hash value generation as a Poisson process.
  • Early Termination: By maintaining a heap of the current maximum signature values ($h_{max}$), the algorithm can stop processing an element as soon as the next generated point exceeds $h_{max}$.
  • In-Order Generation: A binary search approach over weight ranges allows skipping irrelevant intervals.
Algorithm 6: BagMinHash 1 pseudocode illustrating the Poisson process approach and early termination logic.

Evaluation and Results

The algorithm was evaluated using synthetic datasets to verify statistical unbiasedness against ground-truth Jaccard similarities. Test cases ranged from simple pairs to complex distributions, with signature sizes up to 16,384.

Performance and Accuracy

BagMinHash provides massive speedups for large input sizes ($n > 10,000$) and remains efficient even for $n$ as low as 100. Crucially, it maintains statistical independence, a property many competing "fast" sketches sacrifice.

Comparison of BagMinHash against ICWS and other recent algorithms. The table highlights the statistical accuracy (MSE) and identifies significant biases (high z-scores) in several competing methods.

As shown in the table above, BagMinHash's MSE values align perfectly with theoretical predictions. In contrast, algorithms like CCWS, PCWS, and $I^2CWS$ exhibit high z-scores, indicating significant statistical bias in their estimates.

Conclusion

BagMinHash represents a significant advancement in weighted set sketching. By combining the efficiency of Poisson processes with rigorous statistical foundations, it overcomes the $O(mn)$ bottleneck of ICWS without the accuracy trade-offs seen in other recent proposals. While more complex to implement, its scalability makes it the new state-of-the-art for large-scale similarity estimation.

Summary updated

BibTeX
@inproceedings{ertl2018bagminhash,
  author = {Otmar Ertl},
  title = {{BagMinHash - Minwise Hashing Algorithm for Weighted Sets}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2018},
  doi = {10.1145/3219819.3220089},
}
Figure