Reservoir Sampling

Drawing a uniform random sample of fixed size from a stream of unknown length in a single pass.

Sampling a stream

Reservoir sampling selects k items uniformly at random from a stream whose total length n is unknown or too large to store. It keeps a reservoir of k items and, as each new item arrives, decides probabilistically whether to admit it, guaranteeing that after processing every item, all k-subsets are equally likely, in one pass and O(k) memory.

Algorithm R

Kronos motion — classical

Fill the reservoir with the first k items. For the i-th item (i > k), keep it with probability k/i by choosing a random index in [0, i); if that index is below k, replace that reservoir slot. A short induction shows every item seen so far remains in the reservoir with probability exactly k/i, which is uniform.

Implementation

python

import random

def reservoir(stream, k):
    res = []
    for i, item in enumerate(stream):
        if i < k:
            res.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                res[j] = item
    return res

Refinements

Algorithm L skips ahead by drawing the number of items to ignore from a geometric-like distribution, reducing random draws to O(k log(n/k)).
Weighted reservoir sampling (A-Res) assigns each item a key equal to a random number raised to the inverse of its weight and keeps the top k.
Distributed reservoir sampling merges per-shard reservoirs while preserving uniformity.

Uses

Reservoir sampling underlies log sampling, telemetry, and randomized load shedding, and it is a building block in streaming analytics where the data cannot be replayed or stored. It is the streaming counterpart to a uniform random shuffle.