EADS Talk by Alan Roytman – University of Copenhagen

EADS Talk by Alan Roytman

Zero-One Laws for Sliding Windows and Universal Sketches


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 toapproximate 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.

Joint work with Vladimir Braverman and Rafail Ostrovsky.