Overview
Reservoir Sampling keeps a sample reservoir and gives each stream item a fair chance to replace an earlier sample.
FoundationSource checked
Reservoir Sampling
Selects a fixed-size random sample from a stream of unknown length.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Streaming Sampling
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
fixed-size reservoirstream positionreplacement probabilityunknown lengthrandom drawsample selectionsequential scanstreaming sampling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(k)
When to Use
- Use it when a uniform sample is needed from a stream of unknown or very large length.
- Use it when storing the entire population is impossible.
- Use it when a fixed sample size should be maintained online.
When Not to Use
- Avoid it when the population size is known and random indexing is cheaper.
- Avoid it when stratified or weighted sampling is required without modifying the method.
- Avoid biased random sources or untracked seeds in reproducible pipelines.
What It Does
- Samples from a stream
- Keeps fixed memory use
Use Cases
- Sampling logs
- Large data streams
- Unknown-size datasets
Inputs
- Stream of items
- Sample size
Outputs
- Uniform random sample
Key Formulas (1)
Replacement probability
p = reservoirsize / itemsseen
p = reservoir_size / items_seenKeeps each stream item with equal probability.
Pseudocode
- 1.Fill the reservoir with the first k items
- 2.For each later item at position i:
- 3.Choose a random number from 0 through i
- 4.Replace that reservoir position if the number is less than k
- 5.Return the reservoir after the stream ends
Canonical Example
- Input
- stream = [A, B, C, D], k = 2
- Output
- two items selected with equal probability over all stream items
- Explanation
- The reservoir starts with A and B, then later items may replace existing sample positions with decreasing probability.
Implementation Notes
- Fill the reservoir with the first k items.
- For item i after that, choose a random integer from 0 through i and replace only if it is less than k.
- Be explicit about whether i is zero-based or one-based in the probability calculation.
Common Pitfalls
- Using the wrong replacement probability for the current stream index.
- Starting index counts at the wrong value after filling the reservoir.
- Assuming reservoir sampling gives stratified or weighted samples by default.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow stream items sometimes replacing entries in a fixed reservoir.
Step 1 of 5: Fill the reservoir with the first k items
stream-reservoirNotes
Reservoir sampling gives each item equal inclusion probability without knowing the final stream length.
Sources (2)
What each reference supports for this entry.
Vitter Reservoir Sampling
PaperReference for reservoir sampling algorithms over streams of unknown length.
Open sourceThe Art of Computer Programming, Volume 2
BookRandomness reference for Reservoir Sampling's uniformity argument, recurrence, or random-selection procedure.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborFisher-Yates Shuffle
Both maintain uniform random selection over discrete items.
Alternative toStratified Sampling
Reservoir sampling handles streams, while stratified sampling controls group coverage.
Related Algorithms
Tags
RandomnessSamplingLinear Scan