Continuous flow of data
Data / Knowledge library
Reservoir Sampling
Selects a uniform sample from a stream of unknown or large length
Why learn Reservoir Sampling?
It uses bounded memory without knowing the final item count
The problem it solves
It samples streaming data that cannot be stored in full
Where it came from
Reservoir Sampling is a algorithm that selects a uniform sample from a stream of unknown or large length. Its guarantees and tradeoffs depend on the concrete implementation and operating context.
Build your understanding
Work through these exercises in order. Try the task before opening a reference.
- Define Reservoir Sampling and distinguish it from a neighboring concept.
- Choose a realistic task where Reservoir Sampling is appropriate.
- Identify a failure mode caused by misusing Reservoir Sampling.
- Interpret a small design or result involving Reservoir Sampling.
- Explain one tradeoff or limitation of Reservoir Sampling.
Documentation and sources
- NIST Dictionary of Algorithms and Data Structures (xlinux.nist.gov)
Connect the ideas
Explore next
Real World Example
Real-time Telemetry Representative Sampling
IoT sensor network operators managing high-velocity data streams.
The business problem
Storing every data point from millions of sensors is cost-prohibitive, yet simple truncation loses long-term trends and introduces bias toward early data.
How this topic solves it
Reservoir Sampling maintains a fixed-size representative sample of a stream of unknown length, ensuring every element has an equal probability of being selected without needing to know the total stream size in advance.
- Initialize a reservoir array of fixed size k.
- Fill the reservoir with the first k elements from the incoming stream.
- For each subsequent element at index i (where i > k), generate a random integer j between 0 and i.
- If j is less than k, replace the element at index j in the reservoir with the new element from the stream.
The flow shows how incoming stream elements are either accepted into the reservoir or discarded based on a probability calculation.
First k elements
Probability logic (k/i)
Fixed-size sample storage
Rejected elements
- Stream Source → First k items → Initial Fill
- Initial Fill → Populate → Reservoir
- Stream Source → Subsequent items → Random Selection
- Random Selection → Replace item → Reservoir
- Random Selection → Drop item → Discard
Expected business outcome
A statistically unbiased subset of the total stream that allows for accurate trend analysis without the storage overhead of the full dataset.
Limitations and checks
The primary limitation is that it assumes a uniform distribution of importance across the stream; it cannot prioritize recent data or specific event types without modifying the probability logic, which can be checked by verifying if the sample distribution matches the historical stream distribution over time.