(Learned) Frequency Estimation Algorithms under Zipfian Distribution

Abstract

\begin{abstract} The frequencies of the elements in a data stream are an important statistical measure and the task of estimating them arises in many applications within data analysis and machine learning. Two of the most popular algorithms for this problem, Count-Min and Count-Sketch, are widely used in practice. In a recent work [Hsu et al., ICLR'19], it was shown empirically that augmenting Count-Min and Count-Sketch with a machine learning algorithm leads to a significant reduction of the estimation error. The experiments were complemented with an analysis of the expected error incurred by Count-Min (both the standard and the augmented version) when the input frequencies follow a Zipfian distribution. Although the authors established that the learned version of Count-Min has lower estimation error than its standard counterpart, their analysis of the standard Count-Min algorithm was not tight. Moreover, they provided no similar analysis for Count-Sketch. In this paper we resolve these problems. First, we provide a simple tight analysis of the expected error incurred by Count-Min. Second, we provide the first error bounds for both the standard and the augmented version of Count-Sketch. These bounds are nearly tight and again demonstrate an improved performance of the learned version of Count-Sketch. In addition to demonstrating tight gaps between the aforementioned algorithms, we believe that our bounds for the standard versions of Count-Min and Count-Sketch are of independent interest. In particular, it is a typical practice to set the number of hash functions in those algorithms to $\Theta (\log n)$. In contrast, our results show that to minimize the \emph{expected} error, the number of hash functions should be a constant, strictly greater than $1$.

References in corpus (9)

• Learning Combinatorial Optimization Algorithms over Graphs
• Compressed Sensing using Generative Models
• Improving Online Algorithms via ML Predictions
• Learning to Branch
• A Model for Learned Bloom Filters, and Optimizing by Sandwiching
• Learning-Based Low-Rank Approximations
• Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
• Pandora's Box with Correlations: Learning and Approximation
• Composable Sketches for Functions of Frequencies: Beyond the Worst Case

Cited by in corpus (7)

• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• A survey of sketches in traffic measurement: Design, Optimization, Application and Implementation
• Faster Matchings via Learned Duals
• Composable Sketches for Functions of Frequencies: Beyond the Worst Case
• Learning-augmented count-min sketches via Bayesian nonparametrics
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Learning Based Distributed Tracking