Abstract
I will talk about a beloved problem of the workshop attendees: frequency estimation in a stream. The work of Hsu et al. has shown that classical streaming algorithms can be augmented with heavy-hitter predictions to greatly improve their performance. I will talk about a new algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al without the use of any predictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance compared to prior classical and learned approaches.
This is joint work with Anders Aamand, Justin Y. Chen, Huy Nguyen, and, Ali Vakilian, and will appear in NeurIPS ’23.