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.
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.
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