Piotr Indyk (MIT)

The sublinear world of data stream algorithms

In this talk I will describe some of the recent development in the area of data stream algorithms. In this model of computation, the data needs to be processed ''on-the-fly'', using only one pass over the data; moreover, the data size exceeds the available memory by orders of magnitude. Computing over data streams is of growing importance, due to the abundance of massive data sets such as network traffic data.

Probabilistic techniques play crucial role in designing data stream algorithms. In this talk I will give an overview of the methods and tools developed for that purpose.