Discrete Mathematics and Optimization Seminar

Andrew McGregor
University of Pennsylvania
Monday April 3rd at 4.30pm
Burnside 1205

Title. Stochastic Data Streams.

Abstract. Data streams are ubiquitous. Sometimes data is processed as a stream by necessity;
when estimating statistics about network traffic flowing past a router, it is infeasible
to store all the data and run conventional algorithms. In other situations,
data is processed as a stream by choice; being able to process data as it arrives, in the
order it arrives, facilities the design of more efficient distributed systems and systems
that are heavily dependent upon external memory devices. A rich theory of the streaming
model has evolved over the last ten years. In this talk we will present new algorithmic
results and explore some new directions in the study of data streams. One of the main
tenets of the talk will be that massive data streams can often be modeled as if stochastically generated.