\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt

Streaming

Model:

Key idea: sampling

Wait: how do we sample?

Frequent Items

Simple example: frequent items

Discussion:

Sketches

Count-min sketches

More generalizations:

Distinct Items

Natural question: how many distinct items in stream?

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

What if items not random? Randomize!

Min-wise independence