Reservoir Sampling

Why it matters

Reservoir sampling handles unknown streams. Powers log sampling, analytics, and ML training pipelines.

The architecture

Fill reservoir with first k.

For item i>k, replace with prob k/i.

Result is uniform over all seen items.

How it works end to end

Algorithm R by Vitter (1985).

One pass, O(k) memory.

Uniform over full stream.