Reservoir Sampling
Subject: Computer and Technology noun /ˈrɛz.ər.vwɑːr ˈsæm.plɪŋ/ 1 definition
- probabilistic-algorithms
- algorithm-design
- stream-processing
- computer-science
-
Definition (noun)
Entry #292 · UpdatedReservoir Sampling is a family of randomized, single-pass algorithms for selecting a simple random sample of
kitems without replacement from a dataset or data stream whose total sizenis unknown upfront or too large to fit in memory. In the classic formulation (Algorithm R), the algorithm initializes a fixed-sizek-element buffer—the reservoir—with the firstkitems, then for each subsequenti-th item (i > k) generates a uniform random integerjin[1, i]and replaces thej-th reservoir slot wheneverj <= k. Because each arriving item enters with probabilityk / iand each existing reservoir item survives stepiwith probability1 - 1 / i, induction guarantees that every element seen among the firstiitems has an exactk / iprobability of occupying the reservoir. Operating inO(k)memory with a single sequential scan, reservoir sampling enables unbiased sampling over unbounded logs and event streams, though workloads requiring recency bias, arbitrary item deletions, or distinct-key deduplication need specialized variants.Common Forms
Standard Unweighted (Algorithm R): Processes every item after the initial
kentries with one uniform random draw per element inO(n)time, providing a simple baseline when stream rates are moderate and per-item RNG calls are inexpensive.Optimal Gap-Skipping (Algorithm L / Vitter's Algorithm Z): Samples geometric jump distances directly from the acceptance distribution instead of drawing a random number for every item, reducing random-number generation calls to
O(k(1 + log(n / k)))and enabling fast index skips across seekable files or arrays.Weighted Reservoir Sampling (A-Res / Chao's Algorithm): Incorporates per-item weights
w_iso higher-weight items enter the sample proportionally more often, typically by retaining thekitems with the largestu_i^(1 / w_i)keys in a min-heap (Efraimidis–Spirakis) or scaling replacement probabilities by cumulative weight.Distributed Reservoir Sampling: Partitions high-throughput streams across parallel workers that maintain local
k-element reservoirs—commonly keyed by uniform random priorities or paired with partition countsn_p—and merges them via a global top-kheap or count-weighted resampling.
Example
A telemetry collector consumes an unbounded
logs.ingestKafka topic of HTTP access events and maintains an in-memory reservoir array ofk = 1,000JSON records for payload inspection without persisting the full stream. After filling the buffer with the first1,000messages, when the 50,000th event (idx = 49999) arrives (200 OKon/v1/checkout), the worker draws a uniform integerjin[0, 49999]and setsreservoir[j] = eventonly ifj < 1000(a2%replacement probability), maintaining an exact1/50inclusion probability for every event seen so far in constantO(k)memory.