Sketching Algorithms

Sketching Algorithms

Abstract: 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. Work on sketching and streaming started in the late 70s and early 80s with algorithms such as the Morris approximate counter, Flajolet-Martin probabilistic counting ("distinct elements"), the Munro-Paterson rank/select algorithms, and the Misra-Gries 'Frequent' algorithm, paused for a bit until the mid 1990s, and has maintained steam again since the 1996 work of Alon, Matias, and Szegedy. Despite decades of work in the area, some of the most basic questions still remain open or were only resolved recently. In this talk, I survey recent results across a wide variety of sketching topics, some old and some new.

Bio: Jelani Nelson is Professor in Department of EECS 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.