Reservoir Sampling — Random Sampling from a Stream of Unknown Size

Why Reservoir Sampling Matters

Many real-world data scenarios involve streams where the total number of items is unknown or too large to store. How do you select a random sample from a sequence when you don't know its length? Reservoir sampling solves this elegantly.

Why this matters for your career:

• Streaming data is everywhere: server logs, user events, sensor data, database queries
• Reservoir sampling lets you maintain a representative sample without storing the entire dataset
• Used in databases (PostgreSQL ANALYZE sampling), MapReduce, and data pipelines
• Proven technique for handling big data with limited memory — a key skill for data engineers

What Is Reservoir Sampling?

Reservoir sampling is a family of randomized algorithms for randomly selecting k items from a list S of n items, where n is either unknown or very large. The algorithm makes a single pass over the data and uses O(k) memory.

How It Works (k = 1)

1. Store the first item in the reservoir
2. For the i-th item (starting from i=1), replace the reservoir with probability 1/i
3. After processing all n items, each item has probability 1/n of being in the reservoir

How It Works (general k)

1. Store the first k items in the reservoir
2. For the i-th item (i > k), select it with probability k/i
3. If selected, replace a randomly chosen reservoir element
4. After processing all n items, each item has probability k/n of being in the reservoir

Implementation

import random

def reservoir_sample(stream, k):
    """
    Select k random items from a stream.
    Uses O(k) memory regardless of stream length.
    """
    reservoir = []

    for i, item in enumerate(stream):
        if i < k:
            # Fill the reservoir initially
            reservoir.append(item)
        else:
            # Randomly replace elements with decreasing probability
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item

    return reservoir

Example Usage

# Simulate a stream of 1 million items
stream = range(1_000_000)
sample = reservoir_sample(stream, 10)
print(f"Sample: {sample}")
# Output (random): [438912, 129384, 876543, ...]

# Verify randomness: histogram of positions
from collections import Counter

def verify_randomness(stream_size, k, trials):
    positions = Counter()
    for _ in range(trials):
        stream = range(stream_size)
        sample = reservoir_sample(stream, k)
        for item in sample:
            positions[item] += 1
    return positions

results = verify_randomness(1000, 10, 1000)
avg_count = sum(results.values()) / len(results)
print(f"Average count per item: {avg_count:.2f} (expected: {10 * 1000 / 1000:.2f})")
# Output: Average count per item: 10.01 (expected: 10.00)

Mathematical Proof

Claim: After processing n items, each item has probability k/n of being in the reservoir.

Proof sketch for k = 1:

• Item 1 survives if never replaced: P(1) = (1 - 1/2) * (1 - 1/3) * ... * (1 - 1/n) = 1/n
• Item i survives if: selected at step i (1/i) AND not replaced later: (1 - 1/(i+1)) * ... * (1 - 1/n) = 1/n

This elegant property makes reservoir sampling optimal for stream sampling.

Weighted Reservoir Sampling

In many applications, items have different weights — you want items with higher weight to have higher selection probability:

def weighted_reservoir_sample(stream, k):
    """
    Reservoir sampling where each item has a weight.
    Items are (value, weight) tuples.
    """
    reservoir = []
    total_weight = 0

    for value, weight in stream:
        total_weight += weight
        if len(reservoir) < k:
            reservoir.append((value, weight))
        else:
            # Probability of inclusion proportional to weight
            prob = weight / total_weight
            if random.random() < prob * k:
                # Replace a uniformly random item
                idx = random.randint(0, k - 1)
                reservoir[idx] = (value, weight)

    return [v for v, w in reservoir]

Applications

| Domain | Application | |--------|-------------| | Databases | PostgreSQL ANALYZE samples rows for statistics | | Big Data | MapReduce samplers for data skew detection | | Data Science | Maintain representative subset of training data | | Network Monitoring | Sample packets from high-speed network streams | | A/B Testing | Random assignment of users to control/treatment | | Survey Sampling | Representative sampling from large populations | | Machine Learning | Mini-batch selection from streaming data | | Log Analysis | Random subset of logs for debugging and analysis |

Comparison with Other Sampling Methods

| Method | Memory | Passes | Requires n | Suitable for Streams | |--------|--------|--------|-----------|---------------------| | Reservoir Sampling | O(k) | 1 | No | ✅ Yes | | Full Shuffle + Take | O(n) | 1 | Yes | ❌ No | | Random Sort + Take | O(n) | 1 | Yes | ❌ No | | Systematic Sampling | O(1) | 1 | Yes | ⚠️ Yes, but bias risk | | Stratified Sampling | O(k) | 2 | Yes | ❌ No |

Reservoir sampling is the only method that works with unknown n in a single pass with O(k) memory.

Common Pitfalls

| Pitfall | Problem | Solution | |---------|---------|----------| | Using modulo for random selection | Bias when k doesn't divide n | Use proper random integer | | Not seeding RNG | Reproducibility issues | Seed for testing, don't for production | | Incorrect weight handling | Weighted bias not proportional | Use exponential or alias method | | Forgetting k > n | Empty or undersized reservoir | Handle gracefully | | Reservoir modification during iteration | Corruption | Make a copy if needed |

Summary

Reservoir sampling is a clever and mathematically elegant algorithm for selecting a random sample from a stream of unknown or infinite size. It uses O(k) memory regardless of stream length and guarantees each element has equal probability of being selected. It is essential for big data, database statistics, and streaming applications.

Key takeaways:

• Reservoir sampling selects k random items from a stream of unknown length
• Uses O(k) memory, makes a single pass, no need to know n beforehand
• Each item has probability k/n of being in the final sample
• Weighted version handles items with different importance
• Built into PostgreSQL, MapReduce, and many data pipeline tools
• Simple to implement but mathematically rigorous

What's Next: Randomized Min-Cut

The next chapter covers Karger's randomized algorithm for finding the minimum cut in a graph — a surprising and elegant use of random sampling in graph theory.

Extended Example: Distributed Reservoir Sampling

In big data systems, data is often distributed across many machines. Each machine has a portion of the stream. How do you sample from the entire dataset without moving all data to one machine?

def distributed_reservoir_sample(shards, k):
    """
    Reservoir sampling across multiple data shards.
    Each shard produces a local sample, then we merge.
    """
    # Step 1: Each shard produces a reservoir sample
    local_samples = []
    for shard in shards:
        local_sample = reservoir_sample(shard, k)
        local_samples.extend(local_sample)

    # Step 2: Merge by re-sampling
    # The merged sample has size up to len(shards) * k
    # Run reservoir again to reduce to exactly k
    final_sample = reservoir_sample(local_samples, k)
    return final_sample

This technique is used in Google's MapReduce framework, Apache Spark, and other distributed data processing systems. Each machine samples independently, and the coordinator re-samples the union.

Why This Works

The key insight is that independent reservoir samples from each shard can be merged by sampling again. The final sample is statistically equivalent to a reservoir sample from the entire dataset, because each original item had equal probability of being in the merged sample.

Summary

Reservoir sampling is a cornerstone algorithm for big data processing. Its ability to sample from streams of unknown length with fixed memory makes it indispensable for database statistics, data pipelines, and distributed systems.