Algorithms and Complexity Seminar

Monday, May 5, 2008, 4:00-5:15pm in 32-G575.

Streaming Computations on Sliding Windows

Vladimir Braverman (UCLA)

A streaming model is one where data items arrive over long periods of time, either one item at a time or in bursts. Maintaining statistics and aggregates is an important and non-trivial task in this model. This becomes even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. This talk covers two recent results for the sliding windows model.

"Smooth histograms for sliding windows" is a joint work with Rafail Ostrovsky (FOCS¡¯07). This paper presents a smooth histogram method that not only captures and improves multiple previous results on sliding windows, but also extends the class of functions that can be approximated on sliding windows.

"Succinct sampling on streams" is a joint work with Rafail Ostrovsky and Carlo Zaniolo (submitted). We call sampling algorithms succinct if they use provably optimal worst-case memory. In this paper we ask the following question: Is succinct sampling on streams (or S3) possible, and if so, for what models? We show that S3 algorithms are possible for all variants of the problem, i.e., both with and without replacement and both for one-at-a-time and bursty arrival models.

Host: Piotr Indyk

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)