CountSketches, Feature Hashing and the Median of Three

Kasper Green Larsen, Rasmus Pagh, Jakub Tetek

Abstract

CountSketch is a fundamental algorithm for frequency estimation in data streams. While practitioners often use a small, fixed number of rows (typically three) to achieve high accuracy, standard theoretical bounds suggest that many more rows are needed for significant reliability gains. In this work, we bridge this gap by proving that the "Median of Three" approach fundamentally changes the error scaling from $O(1/s)$ to $O(1/s^2)$, where $s$ is the number of columns. This provides a theoretical foundation for the empirical success of small-row CountSketches.

Introduction

In large-scale data processing, sketching algorithms like CountSketch are essential for summarizing massive vectors into a compact memory footprint. A standard CountSketch estimates vector entries by hashing them into $s$ buckets with random signs. To improve reliability, multiple independent rows are often used, with the final estimate being the median of the individual row estimates.

While traditional analysis suggests that $O(\log 1/\delta)$ rows are required to achieve a failure probability $\delta$, empirical evidence shows that using just three rows ($t=2$ in the $2t-1$ median formulation) provides exceptional performance. This paper explores why this "Median of Three" trick is so effective.

Theoretical Framework: The $1/s$ to $1/s^2$ Transition

The core contribution is a new analysis of the moments of the median of independent estimators. The authors prove a general theorem regarding the $q$-th moment of a median, which they then apply to the CountSketch variance.

For a single-row CountSketch (or Feature Hashing), the variance of the estimate $\hat{v}_j$ is bounded by $O(\|v\|_1^2/s)$. By taking the median of three rows, the authors demonstrate that the expected squared error improves to $O(\|v\|_1^2/s^2)$. This asymptotic shift means that doubling the memory (columns $s$) results in a four-fold reduction in variance for three rows, compared to only a two-fold reduction for a single row.

Log-log plot of variance vs. number of columns $s$. The steeper slope for the $t=2$ (3 rows) case compared to $t=1$ (1 row) illustrates the transition from $1/s$ to $1/s^2$ scaling.

Empirical Validation

The theoretical findings were tested across several datasets, including the Kosarak click-stream dataset, Sentiment140 tweets, and synthetic Zipfian distributions. On the Kosarak dataset with $s=512$, the variance for the median-of-three estimator was found to be over 200 times lower than that of the single-row estimator. This massive improvement confirms that the median is highly effective at filtering out noise from hash collisions.

Plot of $s^2 \times \text{variance}$ against $s$. The relative stability of the $t=2$ curve confirms that the variance scales inversely with the square of the number of columns.

Discussion and Limitations

While the Median of Three offers significant stability, it introduces a trade-off: the loss of linearity. Unlike single-row CountSketches, the median operator is non-linear, which may prevent its use as a direct replacement in certain machine learning applications like SVM kernels that rely on linear projections.

Furthermore, the $1/s^2$ behavior becomes most apparent when the number of columns $s$ is large relative to the distribution's "heaviness." In some experiments, such as with the News20 dataset, very large values of $s$ were required to clearly observe the predicted scaling.

Conclusion

The "Median of Three" is more than just a heuristic; it is a mathematically sound method for achieving superior error scaling in sketching algorithms. By shifting the variance from $1/s$ to $1/s^2$, it allows practitioners to achieve high-precision estimates with minimal additional computational overhead.

Summary updated

BibTeX
@inproceedings{larsen2021countsketches,
  author = {Kasper Green Larsen and Rasmus Pagh and Jakub Tetek},
  title = {{CountSketches, Feature Hashing and the Median of Three}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=r-0tOmJsUa},
}
Figure