(Track1) Sketching and Streaming Algorithms

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.