Streaming

Model:

• Huge amount of data
• Can't afford random access
• Instead, read in a stream (sequential access).
• E.g., tapes
• Even for data on disk, sequential much faster
• On disk, can do multiple passes
• Sometimes, even too much to store
  • Stream generated online, must analyze as it goes past
  • Stock market
  • Network routers
  • Sensor network data
  • Telephone billing records
• Model posits stream length $n$ (unknown)
• which makes $\log n$ a natural limit (e.g. to count length of stream).

Key idea: sampling

• What fraction of $n$ stream entries have property $P$?
• if know $P$ in advance, compute as you go
• what if want to ask about unknown $P$ later?
• Choose random sample of size $k$
• Let $x$ be number in sample with property $P$
• Estimate as $nx/k$
• Analysis
  • Suppose $pn$ have property $P$
  • Assume choosing with replacement
  • Then each choice has $P$ with probability $p$
  • So expected number having $p$ is $pk$
  • We see $x$. If $x\in(1\pm\epsilon)kp$, then estimate is $\epsilon$-accurate.
  • Chernoff bound on $\epsilon$ error: $2e^{-\epsilon^2 kp/3}$
  • So, if $kp$ large, probability of error is small
  • in particular, $kp=\mu_{\epsilon,\delta}$ gives $(\epsilon,\delta)$-approximation
  • e.g. $O(\log n)$ space for constant error w.h.p. in $n$.

Wait: how do we sample?

• Reservoir method
• Keep pool of size $k$
• Incorporate first $k$ items
• When $k+1$'st arrives, it should be in sample with prob $k/(k+1)$
• Put it in with that probability
• And evict someone random
• Generalize:
  • When $n^{th}$ item arrives, put it in with prob. $k/n$
  • Evict someone random if so
  • By induction, reservoir contains random sample of items seen so far.
  • Then we include last item with right probability
  • Whether or not included, remainder of reservoir is random subset of prior items

Frequent Items

Simple example: frequent items

• Suppose want to find all items that occur more than $t$ times
• From above, property of being a particular item has fraction $p=t/n$
• Intuitively, need enough samples to expect to see item: i.e. $n/t$
• To avoid errors, need more.
• Choose $k=(8n/t\epsilon^2)\log(n)$
• Then $kp=(8/\epsilon^2)\log n$
• So odds of $\epsilon$ deviation are $(1/n)^{2}$ for particular item
• At most $n/t$ “frequent” items, so odds any deviate are $1/n$
• So can collect any item that shows up more than $(1-\epsilon)kp$ times
• This will also have some false positives.
• But same Chernoff bound shows any item with few representatives unlikely to be sampled enough
• In particular, with high probability no item with less than $(1-\epsilon)^2 t$ occurrences will be included.

Discussion:

• For this particular problem (most frequent) there's a better algorithm
• It just needs $n/t$ space for exact answer
• Nice thing about sample, though, is that you can decide what question to ask after you collect the sample
• Can we beat $n/t$? No: lower bound says that if most frequent item is rare, you need tons of space to find it.

Sketches

Count-min sketches

• Already saw how to count frequent items
• What if can also subtract in stream (but stay positive)? (turnstile model)
• Sketch: hash to $k$ buckets, accumulate in $h(x)$
• If no collisions, get good count.
• If $S$ is total weight, in expectation only $S/k$ collides
• So, get (over) estimate to within additive $2S/k$ with probability $1/2$
• What if want better odds? Use more counters!
• Take $c$ counters, take minimum result
• Probability of error $2^{-c}$
• General: need $O((1/\epsilon)\ln 1/\delta)$ counters (each taking $O(\log n)$ space) for $(\epsilon,\delta)$ approx.
• Can also subtract items from sketch in obvious way.
• Sketch will accurately estimate number of items as long as net count of each item is positive.
• another advantage: sketches can be combined (just add them).

More generalizations:

• Maintaining stats over a window (expiring items)
• Higher moments (e.g. sum of squares) to estimate db joins

Distinct Items

Natural question: how many distinct items in stream?

• To answer naive way, need space equal number of distinct items
• Sampling doesn't obviously apply: what property do we test?
• But a sampling insight still helps

Suppose items are distinct random reals in $[0,1]$

• Show them spread out
• What changes as more arrive? spacing
• Consider interval $[0,p]$
• If $n$ distinct items, expect $np$ in interval
• If $np =\mu_{\epsilon,\delta}$ get $(1\pm\epsilon)\mu$ with probability $1-\delta$.
• So how about choosing $p$ so that got $\mu$ items?
• Translation: keep smallest $\mu$ items, use to set $p$
• Can we conclude this $p$ is $\epsilon$-accurate?
• Not quite: if expected number for this $p$ is $\mu/(1+\epsilon)$, then its probability of deviating to $\mu$ is a bit more than $\delta$.
• So tweak: wait till see $\mu/(1-\epsilon) \ge (1+\epsilon)\mu$ items.
• This won't happen before $p$
• Also won't happen after $(1+\epsilon)p/(1-\epsilon)$
• So we'll get a $p$ in this interval.
• Multiply by $(1-\epsilon)$

What if items not random? Randomize!

• number up to $m$
• simpler goal: for given $t$, with prob. $1-P$, say yes if above $(1+\epsilon)t$ and no if below $(1-\epsilon)t$
• run in parallel for powers of $(1+\epsilon)$ up to $n$.
• Space multiplies by $(\log n)/\epsilon$.
• For given $t$
  • hash to $t$ space
  • watch items hashing to $0$
  • answer yes if anything does, no otherwise.
• Analysis
  • if $k$ elements, prob. no hits is $(1-1/t)^k$
  • for large enough $t$ this is $e^{-k/t}$
  • for small $\epsilon$, if $k>(1+\epsilon)t$ this is $< 1/e-\epsilon/3$
  • while $k< (1-\epsilon)t$ implies $>1/e+\epsilon/3$
  • replicate to amplify. threshold on whether $1/e$ of the tests pass.

Min-wise independence

• alternative pseudorandom approach
• go back to idea of keeping $k$ smallest-hashing “random” values
• so for that, want a distribution where for any subset each item equally likely to hash to “smallest”
• “min-wise independence”
• people have created (approximately) min-wise independent hash families
• so can use these to simulate true randomness.