CSAIL Event Calendar

[A&C; Seminar] Streaming Computations on Sliding Windows

Speaker: Vladimir Braverman, UCLA
Date: Monday, May 5 2008
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Piotr Indyk, MIT
Contact: Ning Xie, 3-9302, ningxie@csail.mit.edu
Relevant URL: http://people.csail.mit.edu/ningxie/algcomp/vova-abs.html

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.

See other events happening in May 2008