What streaming is

  • Streaming is really just small-space data structures 49:20.
  • Object maintained: a high-dimensional vector x ∈ R^n (or a matrix); this lecture is about a vector problem 49:20.
  • Like any data structure, we want to support updates to x and queries about x 50:16.

The turnstile model

  • Term due to Muthukrishnan, roughly '05 50:16, 51:17.
  • Each update is a pair (i, v) and causes x_i ← x_i + v 51:17.
  • x starts as the zero vector at the beginning of the stream 51:17.

Running example — a router

  • n = number of IP addresses (2^32, or 2^128 for IPv6); x_i = number of packets sent to address i 51:59.
  • Every observed packet is an update (i, 1) 52:30, 52:40.
  • Example queries: what is x_i?, or what is the support size of x (how many addresses received traffic?) 52:40, 53:09.

The goal: beat the trivial solutions

  • Trivial options: remember x (n space) or remember the whole stream (m space, m = stream length) 53:09, 54:04.
  • The goal of a streaming algorithm is much less space than either — a router seeing IPv6 traffic has neither 2^128 space nor room for every packet ever seen 54:04, 55:06.

The problem studied: F₀ (distinct elements)

  • Restricted setting for the rest of the lecture 55:21, 56:05:
    • Only one query type: the support size, denoted F₀ for historical reasons.
    • All updates have v = 1 (in general negative updates would be allowed).
  • Plain-English version: how many distinct IP addresses received traffic today? 56:05.

Exact space of the trivial solutions

  • n bits: a bit string whose i-th bit is 1 if address i was ever seen 56:29.
  • m · log n bits: remember the whole stream, since each element is an index costing log n bits 56:29, 56:47.