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.