Reservoir Sampling

Reservoir sampling is an algorithm for sampling $k$ items uniformly from a stream when the total number of items is unknown or too large to store.

It is useful when data arrives one item at a time and you cannot keep the full dataset in memory.

Intuition

The algorithm keeps a fixed-size reservoir of $k$ samples. Early items are accepted automatically. Later items are accepted with decreasing probability, so every item seen so far has the same chance of being in the reservoir.

Algorithm

1. Put the first $k$ items into the reservoir:

$$R=\{x_1,x_2,...,x_k\}$$

2. For each new item $x_i$ where $i>k$, sample an integer $j$ uniformly from:

$$\{1,2,...,i\}$$

3. If $j\le k$, replace $R_j$ with $x_i$.
4. Otherwise, discard $x_i$.

Why It Works

For any item $x_i$, the probability of being selected when it arrives is:

$$\frac{k}{i}$$

After that, it must survive later replacement steps. The replacement probabilities are designed so that after processing $n$ items, every item has probability:

$$\frac{k}{n}$$

of being in the reservoir.

Use Cases

• sampling logs from a stream
• keeping a random sample from a very large file
• online analytics
• memory-limited data processing
• quick inspection of large datasets

Relation To Sampling Methods

Sampling Methods usually assumes access to a dataset or a known distribution. Reservoir sampling handles the streaming case where the population size may not be known ahead of time.

One-line Interview Answer

Reservoir sampling keeps a uniform random sample from a stream using fixed memory, even when the stream length is unknown.