CS-EE-IE-OPIM Joint Seminar
London School of Economics
December 19, 2012, Wednesday @ 13:40pm @ FENS G029
“Data Stream Algorithms”
Data stream models are proposed to capture the scenarios of processing high-throughput or high-volume data. For example, such scenarios can involve analysis of network traffic going through a very busy network router or computations on a massive data set. In such situations, the random access models of computation do not reflect the reality well.
In data stream models, the input data items are presented to an algorithm one by one in some (randomly or adverserially chosen) order. The algorithm is allowed to make a single pass (or a small constant number of passes) over this data stream. The main characteristic of these models is that the algorithm does not have sufficient storage to store the whole input. More specifically, the size of the memory available to the algorithm is a sublinear function of the input size. Hence, the algorithms usually work by sampling the data items or by somehow summarizing (also called sketching) the data seen so far.
In this talk, we will survey the field of data stream algorithms through some basic problems and algorithms. We will demostrate some simple techniques and tools in this area and learn about the limits of computation in these sorts of scenarios.
Tuğkan Batu has received his B.S. degree in Computer Science from Bilkent University in 1996. He has received his Ph.D. in Computer Science from Cornell University in August 2001. He has held postdoctoral fellow positions at University of Pennsylvania, the University of Texas at Austin, and Simon Fraser University. Since September 2006, he has been a Lecturer in the Department of Mathematics at the London School of Economics.