Variance reduction in frequency estimators via control variates method

Rameshwar Pratap, Raghav KulkarniUAI 2021

Introduction

In large-scale data processing, frequency estimation is a fundamental task used for monitoring network traffic, identifying popular items, and managing databases. However, the industry-standard "sketches"—Count-Min-Sketch (CMS) and Count-Sketch (CS)—often suffer from high variance due to hash collisions. This paper introduces a method to mitigate this noise by applying the classical Control Variate (CV) technique, achieving substantial accuracy gains with negligible overhead.

The Challenge of Stream Hashing

Sketches like CMS and CS summarize massive streams into compact data structures. While memory-efficient, they rely on hashing items into a limited number of buckets. When multiple items hash to the same bucket, "collisions" occur, introducing noise that can lead to significant estimation errors. Traditionally, reducing this variance required increasing the memory footprint (more buckets), which is often impractical in resource-constrained environments.

The Control Variate Solution

The authors propose using the Control Variate method to "correct" these estimation errors. The core idea is to identify a random variable $Z$ (the control variate) with a known expected value $E[Z]$ that is correlated with the estimator $X$. By constructing a new estimator $X_{new} = X + c(Z - E[Z])$, the variance can be minimized by choosing an optimal coefficient $c$.

The paper's key innovation lies in defining $Z$ based on the known properties of the hash functions themselves. Since the hash functions are selected by the user, their statistical properties are known, allowing for a "correction" that subtracts the expected error without needing to know the underlying data distribution beforehand.

Experimental Evaluation

The method was tested on both synthetic datasets and real-world password-frequency data. The results consistently showed that the CV-enhanced estimators provide a much more stable and accurate frequency count.

Comparison of variance between the proposed method and original estimators for CMS and CS.

As shown in the figure above, the variance of the original estimators (blue) grows rapidly as the total frequency of items in the stream ($\|\mathbf{f}\|_1$) increases. In contrast, the variance of the proposed method (red) remains remarkably low and stable. This stability makes the estimators much more robust to "heavy hitters" and background noise.

Sketch ratio for Count-Min-Sketch showing improvement as stream size increases.

Furthermore, the sketch ratio—representing the relative improvement in error—demonstrates that the benefit of the CV method increases as the stream size grows. This suggests that the technique is particularly well-suited for the massive data streams encountered in modern industrial applications.

Conclusion

By leveraging the known randomness of hash functions, the authors have developed a powerful yet simple enhancement for frequency sketches. The Control Variate approach provides a significant reduction in variance without requiring additional memory or complex processing. Future work may explore even more effective control variates and apply this technique to other randomized algorithms like similarity search or matrix sketching.

Summary updated

BibTeX
@inproceedings{pratap2021variance,
  author = {Rameshwar Pratap and Raghav Kulkarni},
  title = {{Variance reduction in frequency estimators via control variates method}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
}
Figure