What is hot, what is not; what is new, what is next?
S. Muthu Muthukrishnan, Rutgers Univ
April 16, 2004

Abstract

There is an emerging theory of "data stream algorithms",
that is algorithms that process very high speed data stream inputs
and estimate various statistics and models. These algorithms typically
produce randomized approximations with provable guarantees and rely on
techniques such as group testing, metric space embeddings, and wavelets.
In this talk, we will present an overview of such algorithmic methods.

Data stream algorithms find key application in IP traffic analysis
at link speeds. We will describe the algorithmic and database-related
challenges in this application, and show the use of the novel
data stream algorithms developed in the past few years. The title
lists some of the analyses we can perform at line speeds.