Whispers in the Data: Exploring Advice-Driven Sketching Algorithms

Abstract

In modern systems, sketching algorithms are a common tool to analyze vast amounts of data. Recent work has explored ways to apply an advice model on top of these algorithms, where machine learning models provide hints when processing elements. This enables these sketching algorithms to provide even better performance as they are guided by the models. This thesis focuses on these sketching algorithms that use advice. I examine and consider the limitations of existing algorithms, then design a new sketching framework to work around these limitations, which I dub the Bucketing sketch. Using this framework, I focus on three key computational challenges: estimating high-frequency moments for increment-only data streams, handling turnstile streams, and quantile estimation for aggregate values. For high-frequency moments (defined as $f(\boldx) = \sum x^d$ for $d > 2$), I prove that my approach can achieve precise estimates using logarithmic space, requiring only minimal assumptions about the underlying data-generating process. The remaining two problems are challenging for existing sketching algorithms; nevertheless, I show strong experimental results for all three problems, highlighting the flexibility and power of the Bucketing sketch.