Introduction
Weighted Jaccard Similarity is a cornerstone metric in machine learning for comparing non-negative data vectors, such as word counts in NLP or pixel intensities in computer vision. As datasets scale in both dimensionality and density, exact computation becomes a bottleneck. While Consistent Weighted Sampling (CWS) is the standard for sparse data, its performance degrades significantly in dense scenarios. Rejection Sampling (RS) offers a theoretical alternative for dense data, but practical implementations have historically struggled with efficiency due to the unpredictable nature of random number generation.
Efficient Rejection Sampling (ERS)
This paper introduces Efficient Rejection Sampling (ERS), a novel approach that optimizes RS for production environments. ERS addresses the limitations of standard RS through two primary mechanisms: early stopping with tabulation and a densification strategy.
Instead of an unbounded search for a "hit," ERS imposes a fixed limit $L$ on the number of attempts. This constraint allows the algorithm to utilize tabulation, where random numbers are pre-computed and stored in a $K \times L$ matrix. This shift from on-the-fly generation to memory lookups provides a massive boost in hardware-level efficiency.
When a hit is not found within $L$ steps, ERS employs a densification procedure. It fills these "empty" hash slots by borrowing values from other non-empty slots using a universal hash function. This ensures a complete hash vector while maintaining the statistical properties required for similarity estimation.
Theoretical Bias and Accuracy
A key concern with early stopping and densification is the introduction of bias. The authors provide a rigorous analysis showing that while a slight upward bias exists, it remains mathematically negligible for practical values of $L$.
As shown in the theoretical plots, the bias is well-controlled even as vector density varies. In empirical tests, ERS achieved SVM classification accuracies nearly identical to exact kernels, confirming that this minor bias does not impact downstream tasks.
Performance Results
ERS demonstrates its true strength in dense data scenarios (non-zeros $d \ge 2^{10}$). In these cases, it achieves:
- 10x to 40x speedup over DartMinHash (a state-of-the-art CWS variant).
- 100x to 1000x speedup over traditional CWS.
- 5x speedup over vanilla Rejection Sampling by eliminating PRNG overhead through tabulation.
Conclusion
ERS successfully bridges the gap between the theoretical benefits of rejection sampling and the practical requirements of high-performance computing. By leveraging tabulation and densification, it provides a robust solution for similarity estimation in dense datasets where traditional methods fail. While CWS remains superior for extreme sparsity, ERS is now the definitive choice for relatively dense high-dimensional data.
Summary updated