TL;DR
This paper introduces a remarkably simple rejection-sampling scheme for Weighted Minwise Hashing (WMH) based on a "red-green map" of data vectors. The method is mathematically exact (unbiased), requires significantly fewer bits for storage (5-9 bits), and can be up to 60,000x faster than previous state-of-the-art algorithms.
What Problem Does This Paper Address?
In the world of big data, comparing massive vectors (like web documents, gene sequences, or image histograms) is a core task. The Jaccard Similarity is the gold standard for these comparisons, and Minwise Hashing (MinHash) is the standard technique used to estimate this similarity quickly.
While standard MinHash works great for binary data (sets), Weighted Minwise Hashing (WMH) is needed for real-valued data. However, WMH has historically been a massive computational bottleneck. The best existing exact method (Ioffe’s Consistent Weighted Sampling) requires $O(d)$ operations per hash, where $d$ is the number of non-zero elements. When you need thousands of hashes for accuracy across millions of vectors, this cost becomes prohibitive. Researchers often had to choose between slow, exact methods or faster, biased approximations.
Methods
The author proposes a new algorithm based on a "Red-Green Map" and rejection sampling.
- The Red-Green Map: Imagine an interval $[0, M]$, where $M$ is the sum of the maximum possible values for each dimension of your data. This interval is divided into segments corresponding to each dimension. Within each segment, a "green" zone is marked representing the actual value of the vector in that dimension, while the remaining space in that segment is "red."
- Rejection Sampling: To generate a hash, the algorithm picks a random point in the total interval $[0, M]$. If the point falls in a "red" zone, it's rejected, and the algorithm tries again. If it falls in a "green" zone, it stops.
- The Hash Value: Crucially, the hash value $h(x)$ is simply the number of attempts it took to hit a green zone.
- Constant Time Lookups: To make this fast, the author uses two pre-computed hashmaps (
IntToCompandCompToM) that allow the algorithm to check if a random point is "green" or "red" in $O(1)$ constant time, regardless of the vector's dimensionality.
This approach ensures that the probability of two different vectors producing the same hash is exactly equal to their generalized Jaccard similarity.
Key Insights and Ideas
- The "Aha" Moment: The number of rejected samples in a carefully constructed rejection sampling scheme follows the exact same distribution required for weighted minwise sampling. This transforms a complex probability problem into a simple "dart-throwing" exercise.
- Effective Sparsity: The runtime doesn't depend on the number of non-zeros ($d$), but on "effective sparsity" ($s_x$), which is the ratio of the vector's $L_1$ norm to the total possible mass $M$. In many real-world datasets, this ratio is favorable, leading to massive speedups.
- Bit-Efficiency: Unlike previous methods that produced 32-bit or 64-bit hash values, this method naturally produces small integers. For the tested datasets, the hashes only required 5 to 9 bits, leading to an 8x saving in memory/storage.
Key Results
The method was evaluated on three real-world datasets representing different scales of dimensionality and sparsity: Hist (RGB histograms), Caltech101 (HOG codes), and Oxford (large-scale HOG codes).
- Speed: On the Oxford dataset, the proposed method was 60,000x faster than Ioffe’s method for computing 500 hashes. Even compared to modern "densified" approximate heuristics, it was roughly 100x faster.
- Accuracy: Because the method is theoretically exact, its estimation error is indistinguishable from Ioffe’s method and significantly better than biased approximation schemes (like Fast-WDOPH).
- Computational Complexity: The expected time to compute a hash is $O(1/s_x)$. As long as the data isn't extremely sparse relative to the maximum possible values, this is much faster than $O(d)$.
Limitations and Future Work
- Sensitivity to Scaling: The performance depends heavily on the "gap" between the actual values and the pre-defined maximum values ($m_i$). If the maximums are set too high, the "red" zones become huge, and the algorithm will spend too much time rejecting samples.
- Very Sparse Datasets: For extremely sparse datasets where the magnitude of components is less important than the sparsity pattern itself, the author notes that binarization and "densified" one-permutation hashing might still be preferable.
- Future Directions: The author suggests that this "locality-sensitive" property of rejection sampling is a new observation that could potentially be applied to other types of randomized algorithms beyond Jaccard similarity.
Summary updated