TALK: Zero-One Laws for Sliding Windows and Universal Sketches

Tuesday, January 19, 2016 - 2:00pm to 3:00pm
Location: 
32-D463 (Star)
Speaker: 
Alan Roytman
Biography: 
Tel Aviv University

Streaming algorithms serve an important role in analyzing vast amounts of data, especially when it is infeasible to store a large part of the input in memory. Given this limited amount of storage, a typical approach is to design a sophisticated algorithm that computes a specific statistic in small space. In this talk, we consider the following fascinating possibility: can we compute many statistics with a single algorithm? This question is even more challenging in the sliding window streaming model, where statistics are only computed over recent data.

Our main result is the design of a “universal” streaming algorithm in the sliding window model that can simultaneously approximate many functions (i.e., statistics) from a broad class of frequency-based monotonically increasing functions. That is, we construct a single summary of the streaming data such that, for any function G taken from the class, the summary can be used to approximate the value \sum_{i=1}^n G(m_i) (here, m_i represents the frequency that element i from a universe of size n appears in the window).

In addition, we give a zero-one law for the class of monotonically increasing functions G that specifies when the summation \sum_{i=1}^n G(m_i) can be approximated in the sliding window model. That is, we define a certain set of properties such that, if a given function G satisfies these conditions, we provide an algorithm that approximates the sum using polylogarithmic memory. Otherwise, we give a super-polylogarithmic lower bound on the memory required for such an approximation.