Algorithms and Complexity Seminar

Thursday, October 18, 2007, 4-5:15pm in 32-G575.

The Order of the Data Stream

Andrew McGregor (UCSD)

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 working 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 on establishing lower bounds that address some of these questions. Highlights include:

  • The first general lower bound for random-order data streams.
  • 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.
    • Includes joint work with Sudipto Guha.

    Host: Piotr Indyk

    (The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)