Skip to main content
Definition Website Computer and Technology

Reservoir Sampling

Subject: Computer and Technology noun /ˈrɛz.ər.vwɑːr ˈsæm.plɪŋ/ 1 definition

  1. Definition (noun)

    Entry #292 · Updated

    Reservoir Sampling is a family of randomized, single-pass algorithms for selecting a simple random sample of k items without replacement from a dataset or data stream whose total size n is unknown upfront or too large to fit in memory. In the classic formulation (Algorithm R), the algorithm initializes a fixed-size k-element buffer—the reservoir—with the first k items, then for each subsequent i-th item (i > k) generates a uniform random integer j in [1, i] and replaces the j-th reservoir slot whenever j <= k. Because each arriving item enters with probability k / i and each existing reservoir item survives step i with probability 1 - 1 / i, induction guarantees that every element seen among the first i items has an exact k / i probability of occupying the reservoir. Operating in O(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 k entries with one uniform random draw per element in O(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_i so higher-weight items enter the sample proportionally more often, typically by retaining the k items with the largest u_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 counts n_p—and merges them via a global top-k heap or count-weighted resampling.

    Example

    A telemetry collector consumes an unbounded logs.ingest Kafka topic of HTTP access events and maintains an in-memory reservoir array of k = 1,000 JSON records for payload inspection without persisting the full stream. After filling the buffer with the first 1,000 messages, when the 50,000th event (idx = 49999) arrives (200 OK on /v1/checkout), the worker draws a uniform integer j in [0, 49999] and sets reservoir[j] = event only if j < 1000 (a 2% replacement probability), maintaining an exact 1/50 inclusion probability for every event seen so far in constant O(k) memory.