Friday, October 12, 10:50am, CSE 3941
Title: The Order of the Data
Stream
Speaker: Andrew McGregor, University of California, San
Diego
Abstract:
Data streams arise in many areas including monitoring network
traffic, query-planning for databases, designing I/O efficient
algorithms, and aggregating sensor network readings. A rich theory
for the data-stream model has been developing over the last ten
years. However, many important questions remain.
In this talk, we investigate issues that pertain to how a stream is
ordered. For example, when evaluating order-invariant functions, does
it require significantly more memory to process a stream that is
adversarially ordered rather than one that is randomly ordered? What
issues arise when trying to evaluate order-dependent functions? In
this talk, we focus of establishing lower-bounds that address some of
these questions. Highlights include:
-- The first general lower bound for random-order data streams. And
it's tight!
-- An exponential separation between the number of passes required
for selection in random-order and adversarial-order data streams.
-- A general approach to proving lower-bounds for multi-pass,
adversarial-order data streams.
-- The first doubly-exponential pass/space trade-off for adversarial-
order data streams. And it's tight!
Includes joint work with Sudipto Guha.