Reservoir, Priority & Bottom-k Sampling

Keeping a Fair Few from an Endless Many

Suppose people enter a theatre one at a time, but only three seats are reserved for a final interview. The total number of arrivals is unknown. Filling the seats with the first three people is easy, but unfair to everyone who arrives later. A streaming sampler must continually reconsider the seats so that, after any number of arrivals, every person has the correct chance of being represented.

This deep dive builds on the prerequisite chapter about approximate counting and sampling. That foundation explains why a sample can replace a full stream for some questions. The missing layer is algorithmic: how do we maintain a fixed-size uniform sample in one pass, support weights, assign stable random ranks, merge samples from partitions, and calculate valid inclusion probabilities for estimation?

Reservoir sampling keeps exactly $k$ items from a stream of unknown length. In Algorithm R, the first $k$ items fill the reservoir. When item $t$ arrives, where $t\gt k$, include it with probability $k/t$ and, if included, replace one uniformly chosen reservoir position. After processing $t$ distinct positions, every item is present with probability $k/t$ and every $k$-subset is equally likely.

Bottom-$k$ sampling gives each item an independent continuous rank $u_i\sim\operatorname{Uniform}(0,1)$ and retains the $k$ smallest ranks. This produces the same uniform fixed-size sample but makes selection deterministic once ranks are attached. It is naturally mergeable: the global bottom $k$ are the bottom $k$ of the union of local bottom-$k$ samples, provided every partition uses the same stable rank function and item identity.

Priority sampling adapts ranking to positive weights. A common construction draws $u_i\sim\operatorname{Uniform}(0,1)$, forms priority $q_i=w_i/u_i$, and keeps the $k$ largest priorities. The next-largest priority becomes a threshold used to estimate weighted subset sums. Weighted sampling is not uniform sampling with a decorative weight column: it changes inclusion probabilities and the estimators required downstream.

For a tiny reservoir example with $k=2$, items A and B fill the sample. Item C is admitted with probability $2/3$ and then replaces A or B with probability $1/2$. Thus C has probability $2/3$ of inclusion, while A survives with probability $1-(2/3)(1/2)=2/3$; the same holds for B. Fairness is restored after just one update.

The questions that drive a design are therefore specific. Are stream positions or distinct entities being sampled? Is the target uniform over items, proportional to weight, or optimized for subset-sum estimation? Must partitions merge exactly? Can the same entity appear repeatedly? Are ranks secret from an adversary? Which inclusion probability belongs in the estimator?

Reservoir Invariants and Priority Keys

The reservoir proof is an induction. Immediately after the first $k$ items, each is included with probability 1, equal to $k/k$. Assume that after $t-1$ items, every earlier item is included with probability $k/(t-1)$. At time $t$, the new item is included with probability $k/t$. An earlier item survives unless the new item is admitted and replaces its particular slot:

$$ \Pr[\text{survive step }t]=1-\frac{k}{t}\frac1k=1-\frac1t=\frac{t-1}{t}. $$

Multiplying by its previous inclusion probability gives

$$ \frac{k}{t-1}\frac{t-1}{t}=\frac kt. $$

Thus old and new items share the same marginal inclusion probability. A stronger induction shows every $k$-subset of the first $t$ positions has probability $1/\binom tk$. The proof uses exact uniform choices and treats stream positions as population units. Duplicate values at different positions remain different units unless preprocessing defines entity-level deduplication.

Bottom-$k$ provides another view. Assign independent continuous uniform ranks $u_i$ and retain the $k$ smallest. Symmetry makes every ordering of ranks equally likely, so every $k$-subset is equally likely. Algorithm R and bottom-$k$ therefore produce the same distribution for a single uniform sample, but their operational properties differ. Algorithm R needs only arrival count and reservoir state; bottom-$k$ stores ranks and supports deterministic recomputation and exact distributed merging.

For weighted data, define $q_i=w_i/u_i$ with $w_i\gt0$ and keep the $k$ largest priorities. Let $\tau$ be the $(k+1)$-st largest priority. A retained item receives adjusted weight $\widehat w_i=\max(w_i,\tau)$. Conditional on the other items' threshold, item $i$ is selected when $u_i\lt w_i/\tau$, so its inclusion chance is $\min(1,w_i/\tau)$ and $w_i/\pi_i=\max(w_i,\tau)$. This is the Horvitz–Thompson correction underlying priority estimates of totals and subset sums. The leave-one-out threshold logic matters; treating the observed threshold as an ordinary fixed probability without the priority-sampling proof is unsafe.

Boundary cases expose the assumptions. Discrete or truncated ranks can tie, so the implementation needs a deterministic secondary key that preserves an analyzed ordering. Zero or negative weights are invalid for $w_i/u_i$. Reusing a rank per occurrence instead of per entity changes the population. Public predictable ranks allow an adaptive adversary to manufacture unusually small or large keys.

flowchart TD
    A[Define population units] --> B[Choose uniform or weighted target]
    B --> C{Uniform fixed-size?}
    C -->|arrival update| D[Admit item t with probability k over t]
    D --> E[Replace uniform reservoir slot]
    E --> F[Induction gives inclusion k over t]
    C -->|stable ranks| G[Assign independent uniform keys]
    G --> H[Keep bottom k]
    H --> I[Order symmetry gives uniform k-subset]
    B --> J[Weighted subset sums]
    J --> K[Priority q equals w over u]
    K --> L[Keep top k and threshold next priority]
    L --> M[Adjusted weights via inclusion probability]
    A --> X{Identity randomness and ties specified?}
    X -->|no| Y[Proof invalid or target population changed]
    X -->|yes| B
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,G,H,J,K purple;
    class F,I,L,M teal;
    class X,Y crimson;

Bottom-k Inclusion Probabilities

Let $n$ distinct items receive independent continuous uniform ranks and let $U_{(k)}$ be the $k$-th smallest rank. Symmetry gives each item inclusion probability $k/n$. For cardinality estimation, the order statistic contains more information than the retained identities. Its density is Beta$(k,n-k+1)$, and for $k\gt1$,

$$ \mathbb E\!\left[\frac1{U_{(k)}}\right]=\frac{n}{k-1}. $$

Therefore

$$ \widehat n=\frac{k-1}{U_{(k)}} $$

is unbiased for $n$. When $k\gt2$, its variance is $n(n-k+1)/(k-2)$ under the ideal continuous-rank model. The estimator is undefined for $k=1$ and has infinite variance at $k=2$, showing why tiny bottom-$k$ samples can be mathematically fragile even though inclusion remains uniform.

For estimating a total $T=\sum_i y_i$ from a uniform fixed-size sample, each $\pi_i=k/n$, so the Horvitz–Thompson estimate is $(n/k)\sum_{i\in S}y_i$ when $n$ is known. If $n$ is itself inferred from the same threshold, covariance and estimator design must be handled rather than plugging an estimated $n$ into a formula and assuming unbiasedness.

Rank generation is part of the theorem. Ideal ranks are independent and continuous. Hash-derived finite ranks create ties and limited independence; a stable composite key such as (rank, canonical_item_id) resolves order but does not manufacture missing randomness. Repeated entities require a decision: sample occurrences with fresh keys, or sample entities with one stable key.

from itertools import combinations
from math import comb
from random import Random

def reservoir(items, k, seed=0):
    if not isinstance(k, int) or k < 0:
        raise ValueError("k must be a nonnegative integer")
    rng = Random(seed)
    sample = []
    for t, item in enumerate(items, start=1):
        if t <= k:
            sample.append(item)
        else:
            j = rng.randrange(t)
            if j < k:
                sample[j] = item
    return sample

def bottom_k(items, k, seed=0):
    if not 0 < k <= len(items):
        raise ValueError("k must satisfy 0 < k <= number of items")
    rng = Random(seed)
    ranked = [(rng.random(), index, item)
              for index, item in enumerate(items)]
    return sorted(ranked)[:k]

def merge_bottom_k(local_samples, k):
    candidates = [entry for sample in local_samples for entry in sample]
    return sorted(candidates)[:k]

#Normal deterministic traces.
items = list("ABCDE")
print("reservoir:", reservoir(items, 3, seed=27))
ranked = bottom_k(items, 3, seed=27)
print("bottom-k:", ranked)

#Merge invariant: local bottom-k candidates contain the global bottom-k.
rng = Random(91)
all_ranked = sorted((rng.random(), i, i) for i in range(100))
partitions = [all_ranked[0::4], all_ranked[1::4],
              all_ranked[2::4], all_ranked[3::4]]
locals_ = [sorted(part)[:10] for part in partitions]
assert merge_bottom_k(locals_, 10) == all_ranked[:10]

#Simulation checks uniform inclusion and unbiased threshold estimation.
n, k, trials = 20, 5, 50_000
inclusions = [0] * n
estimates = []
for trial in range(trials):
    sample = bottom_k(list(range(n)), k, seed=trial)
    for _, _, item in sample:
        inclusions[item] += 1
    threshold = sample[-1][0]
    estimates.append((k - 1) / threshold)
rates = [count / trials for count in inclusions]
print("inclusion range / target:", min(rates), max(rates), k / n)
print("mean cardinality estimate:", sum(estimates) / trials)
assert max(abs(rate - k / n) for rate in rates) < 0.008
assert abs(sum(estimates) / trials - n) < 0.3

#Boundary and invalid cases.
assert reservoir([], 3, seed=1) == []
for bad_k in (-1, 0, 6):
    try:
        bottom_k(items, bad_k, seed=1)
    except ValueError as error:
        print("invalid test passed:", error)

Sampling Merges, Weights and Rare Events

In a teaching case, Algorithm R makes invariants visible: learners can enumerate all random branches for $n=4,k=2$ and verify that all six subsets have probability $1/6$. Bottom-$k$ then reframes the same distribution as an ordering problem and introduces order statistics.

At professional scale, a distributed observability platform may need a reproducible sample of unique traces across hundreds of shards. Stable hash-derived ranks and global bottom-$k$ merging are attractive because each shard sends only its local bottom-$k$ candidates. The contract must fix canonical trace identity, hash version, seed, rank width, tie-breaking, deduplication, and window boundaries. If shards use different seeds, their local thresholds are incomparable and the merge guarantee disappears.

Weights arise when bytes, cost, or business impact matter more than record count. Priority sampling can estimate weighted subset sums, while exponential-race keys produce a weighted sample without replacement. These are related but answer different questions. The implementation must retain the threshold information required by its estimator; returning only item IDs may make later unbiased estimation impossible.

Rare events expose a limitation of globally uniform sampling. If errors occur in one per million traces and $k=1000$, many windows contain no errors. Increasing weights after observing outcomes can bias analysis. Better designs predeclare strata, maintain a dedicated error reservoir, or use inclusion probabilities driven by features available at selection time, then apply the corresponding estimator.

Adversarial inputs create another boundary. If clients can predict rank hashes, they may search for IDs with exceptionally small ranks and dominate bottom-$k$. A keyed pseudorandom function and rotation policy may be required, but rotation changes stable identities across windows and complicates merges. Evidence that invalidates deployment includes inclusion-rate drift, rank collisions beyond expectation, shard-dependent sampling rates, lost threshold metadata, merge disagreement with a centralized oracle, or rare-group coverage below its declared requirement.

flowchart TD
    A[Define population and target statistic] --> B{Uniform or weighted?}
    B -->|uniform sequential| C[Reservoir Algorithm R]
    B -->|uniform distributed| D[Stable bottom-k ranks]
    B -->|weighted estimates| E[Priority sampling with threshold]
    A --> F{Rare groups require coverage?}
    F -->|yes| G[Predeclare strata and allocate capacity]
    F -->|no| B
    C --> H[Validate inclusion frequencies]
    D --> I[Validate centralized merge oracle]
    E --> J[Validate adjusted-weight estimates]
    G --> K[Validate per-stratum coverage]
    H --> L{All contracts pass?}
    I --> L
    J --> L
    K --> L
    L -->|yes| M[Deploy and monitor]
    L -->|no| N[Reject or redesign]
    M --> O{Drift attack or metadata loss?}
    O -->|yes| N
    O -->|no| M
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,F navy;
    class C,D,E,G purple;
    class H,I,J,K,M teal;
    class L,N,O crimson;

Choose and Verify a Sampling Scheme

The disciplined workflow begins with the population and query, not the data structure. State whether units are occurrences, entities, or weighted entities; whether sample size or inclusion probability must be fixed; whether distribution and reproducibility matter; and which estimator consumes the sample. Only then choose reservoir replacement, bottom-$k$ ranks, priority keys, Bernoulli sampling, or stratification.

This bridges backward to Bernoulli sampling, expectations, and unbiased estimators. It bridges forward to distinct counting, similarity sketches, distributed summaries, adaptive sampling, survey estimation, and rare-event monitoring. Across those topics, random selection and statistical correction must be designed together.