AF: Small: Improving the streaming fundamentals

A sketch of a dataset is a compressed representation of it that allows for answering some family of queries. A streaming algorithm is then simply a sublinear memory dynamic data structure, where the sketch can then be viewed as the streaming algorithm’s memory footprint. Sketching has found applications in streaming, large-scale linear algebra, distributed algorithms, and machine learning. Despite sketching having been studied in the theory community for more than 45 years, we still do not have optimal algorithms (i.e., using the asymptotically least amount of memory) for some of the most basic problems in the field. This project aims to make progress on many of these fundamental problems. The PI will also engage in K-12 outreach activities, mentor both undergraduate and graduate students on research related to the project, and co-organize workshops. The project aims to make progress on some of the core fundamental problems in streaming, such as heavy hitters, quantiles, moment estimation, sampling from streams, and more. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.