Data Stream Algorithms and Applications
In the data stream scenario, input arrives very rapidly
and there is limited memory to store the input.
In the past few years, researchers in
Theoretical Computer Science, Databases, IP Networking
and Computer Systems have developed new algorithms that work
within these space and time constraints. The methods
rely on metric embeddings, pseudo-random computations and
sparse approximation theory. The applications include IP network
traffic analysis, mining text and spatial streams and
processing massive data sets.
In this paper, I will present an overview of the
principles and the practice of data stream management.
I will also discuss open problems.
S. Muthukrishnan is currently affiliated with AT&T Labs and Rutgers University