![Cleveland](_derived/Cleveland.html_cmp_blitz010_vbtn.gif)
![Friedman](_derived/Friedman.html_cmp_blitz010_vbtn.gif)
![Grunwald](_derived/Grunwald.html_cmp_blitz010_vbtn.gif)
![Jewell](_derived/Jewell.html_cmp_blitz010_vbtn.gif)
![Kolaczyk](_derived/Kolaczyk.html_cmp_blitz010_vbtn.gif)
![Lee, T.](_derived/LeeT.html_cmp_blitz010_vbtn.gif)
![Lee, Y.](_derived/LeeY.html_cmp_blitz010_vbtn.gif)
![Madigan](_derived/Madigan.html_cmp_blitz010_vbtn.gif)
![Meng](_derived/Meng.html_cmp_blitz010_vbtn.gif)
![Muthukrishnan](_derived/Muthukrishnan.html_cmp_blitz010_vbtn_p.gif)
![Nair](_derived/Nair.html_cmp_blitz010_vbtn.gif)
![Nolan](_derived/Nolan.html_cmp_blitz010_vbtn.gif)
![Rus](_derived/Rus.html_cmp_blitz010_vbtn.gif)
![Saul](_derived/Saul.html_cmp_blitz010_vbtn.gif)
![Singer](_derived/Singer.html_cmp_blitz010_vbtn.gif)
![Wainwright](_derived/Wainwright.html_cmp_blitz010_vbtn.gif)
![Wolfe](_derived/wolfe.html_cmp_blitz010_vbtn.gif)
![Wu](_derived/Wu.html_cmp_blitz010_vbtn.gif)
| |
Estimating Simple Statistical Parameters on High Speed Data Streams
Muthu Muthukrishnan
Rutgers University
In a number of applications, input arrives very rapidly and there is
limited memory to store the input. One needs to monitor simple statistical
quantities of such ``streams''.
In the past few years, researchers in Theoretical Computer Science
have developed new estimation 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 message streams for Homeland
Security and processing massive data sets in general.
I will present an overview of the algorithmic principles, and discuss issues
in building data stream systems that work at IP line speeds.
I will also discuss open problems, in particular, in performing more
sophisticated statistical analyses on data streams.
This talk is based on an updated
version of the survey at http://www.cs.rutgers.edu/~muthu/stream-1-1.ps
|