A “sketch” is a data structure supporting some pre-specified set of queries and updates to a database while consuming space substantially (often exponentially) less than the information theoretic minimum required to store everything seen, and thus can also be seen as some form of functional compression. The advantages of sketching include less memory consumption, faster algorithms, and reduced bandwidth requirements in distributed computing environments. A "streaming" algorithm is one that dynamically updates a sketch as data is updated. In this tutorial we sketch (pun intended) a suite of tools from the sketching literature for counting problems, graph problems, finding frequent items, dimensionality reduction, and computational linear algebra, together with a discussion of lower bounds.
Jelani Nelson (UC Berkeley)
Jelani Nelson is Professor in the Department of Electrical Engineering and Computer Science at UC Berkeley. His research interests include sketching and streaming algorithms, dimensionality reduction, compressing sensing, and randomized linear algebra. In the past he has been a recipient of the PECASE award, a Sloan Research Fellowship, and an NSF CAREER award. He is also the Founder and President of a 501(c)(3) nonprofit, “AddisCoder Inc.”, which organizes annual summer camps that have provided algorithms training to over 500 high school students in Ethiopia (see addiscoder.com).
Related Events (a corresponding poster, oral, or spotlight)
2020 Tutorial: (Track1) Sketching and Streaming Algorithms Q&A »
Tue. Dec 8th 09:00 -- 09:50 PM Room