Friday, 16:15 - 16:40 h, Room: H 3012


Mariano Zelke
Algorithmic techniques for data stream computations


For computation on today's massive data, it is not reasonable anymore to assume the existence of a main memory containing the whole input for fast random access. On such data streaming algorithms are appropriate for which fast random access to the input and even its complete storage are dispensable. In contrast, the input is processed in an online fashion using a main memory size that significantly falls below the input data size.
In this talk we present some basic techniques for streaming algorithms which provide the foundation for more elaborate approaches. We illustrate reservior sampling to draw uniform random samples out of a stream of unknown length and sliding window sampling to exclude outdated input items from the sample. Moreover, we show how to approximate the frequency moments of a stream via the technique of AMS sampling and how to estimate the multiplicity of an item in the input stream by using the count-min sketch.


Talk 3 of the invited session Fri.3.H 3012
"Graph optimization problems in the streaming model" [...]
Cluster 2
"Combinatorial optimization" [...]


  personal loan . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.