Login
Computer Science @ Rochester
Monday, May 01, 2006
11:00 AM
CSB 209
Ph.D. Thesis Proposal
Ashwin Lall
University of Rochester
Streaming Algorithms for Network Flow Data Analysis
The algorithmic field of Data Streaming was first proposed over a decade ago by Alon, Matias, and Szegedy. Since then, considerable work has been done in the streaming model of computation. The streaming model is precisely the one we want to use to perform real-time computation on network data because it allows only single pass access to the data and guarantees low memory consumption and processor usage per packet. However, the ideas from the streaming context have been slow to catch on in the networking literature. In this proposal we will seek to catalyze this change by demonstrating both theoretically and empirically that the ideas from streaming algorithms will have a considerable impact on the performance of algorithms for online network analysis. In particular, we present novel algorithms for maintaining counts of large number of items and for computing the entropy of network traffic to demonstrate that streaming algorithms can outperform existing methods. We also propose several new problems that are open and that we will look to solve over the next two years.