STREAMING ALGORITHMS

Streaming algorithms are algorithms designed in a model where only one (or a small constant number of) sequential pass(es) over the data is (are) allowed. The goal is to solve a given problem using significantly less space than the input data size, while processing each data element as fast as possible. The model is motivated by the fact that when processing truly massive datasets, solutions requiring more than one sequential pass over the data are often infeasible (e.g. since random accesses to disk blocks are much slower than sequential accesses). Moreover, in some applications data simply has to be processed sequentially as it is generated.

In recent years, the streaming algorithms area has flourished as the discovery of several novel algorithmic techniques has enabled the enlargement of the class of problems with efficient streaming algorithms. Nevertheless, fundamental gaps remains in the understanding of what problems can be solved in the streaming model.The center considers a number of streaming problems and e.g. investigates the general applicability of already developed streaming algorithms techniques; several fundamental geometric and of graph problems is also considered in variants of the streaming model. Please refer to the centers annual reports for a discussion of obtained result.