Weighted Reservoir Sampling

Imagine you work at a news aggregator. Every second, thousands of articles arrive — each one stamped with a popularity score. Your boss wants a random sample of 10 articles to display, but articles with higher scores should appear more often than obscure ones. The catch: you have no disk space to store the whole stream, and you must always have a ready answer.

This is the weighted reservoir sampling problem. It generalises the classic (uniform) reservoir sampling algorithm — where each item has an equal chance of making the sample — to the case where items carry weights that bias the draw.

The elegant solution, algorithm A-Res (short for Algorithm with a Reservoir), was published by Pavlos Efraimidis and Paul Spirakis in 2006. It processes each item exactly once, keeps a fixed-size reservoir of $k$ candidates, and guarantees that after seeing any prefix of the stream each item's probability of being in the reservoir equals its weight divided by the total weight seen so far.

No second pass. No random-access memory of old items. Just a single priority queue that shrinks naturally as stronger candidates arrive.

The idea connects deeply to randomized algorithms and to the kind of one-pass streaming that makes modern large-scale analytics possible.

Each colored ball in the stream has a weight. A-Res keeps a reservoir of size $k = 3$. Run the algorithm and watch which balls end up in the reservoir — then run it many times to see the empirical frequencies match the weights.

<!-- {{c_intro}} -->
<div class="panel">
  <div class="stream-label">{{label_stream}}</div>
  <div id="stream" class="stream"></div>
  <div class="controls">
    <button id="btn-step" type="button">{{btn_step}}</button>
    <button id="btn-run" type="button">{{btn_run}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="reservoir-label">{{label_reservoir}} <span class="k-label">(k = 3)</span></div>
  <div id="reservoir" class="reservoir"></div>
  <div id="status" class="status"></div>
</div>
<div class="stats-panel">
  <div class="stats-title">{{label_stats}} <span id="run-count">(0 {{label_runs}})</span></div>
  <div id="stats" class="stats"></div>
</div>

/* {{c_css_base}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.panel { margin-bottom: .8rem; }
.stream-label, .reservoir-label, .stats-title {
  font-size: .78rem; font-weight: 700; text-transform: uppercase;
  letter-spacing: .06em; color: #556; margin-bottom: .3rem; }
.stream { display: flex; flex-wrap: wrap; gap: 6px; min-height: 52px; margin-bottom: .5rem; }
.reservoir { display: flex; gap: 8px; min-height: 60px;
  border: 2px dashed #aaa; border-radius: 10px; padding: 6px; margin-bottom: .5rem; }
/* {{c_css_ball}} */
.ball {
  width: 46px; height: 46px; border-radius: 50%; display: flex;
  align-items: center; justify-content: center;
  font: 700 13px ui-monospace, monospace; color: #fff;
  cursor: default; transition: transform .15s, opacity .15s;
  flex-shrink: 0; }
.ball.incoming { opacity: .35; }
.ball.current { opacity: 1; transform: scale(1.15); box-shadow: 0 0 0 3px #f4c; }
.ball.selected { opacity: 1; }
.ball.rejected { opacity: .2; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
  border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; color: #333; }
/* {{c_css_stats}} */
.stats-panel { border-top: 1px solid #dde; padding-top: .5rem; }
.stats { display: flex; flex-wrap: wrap; gap: 6px; }
.stat-bar { display: flex; flex-direction: column; align-items: center; gap: 2px; }
.bar-track { width: 46px; height: 70px; background: #eef; border-radius: 4px;
  display: flex; align-items: flex-end; overflow: hidden; }
.bar-fill { width: 100%; background: #1d3557; border-radius: 4px 4px 0 0;
  transition: height .3s; }
.bar-label { font-size: .7rem; font-weight: 700; color: #556; }
.bar-pct { font-size: .68rem; color: #778; }
.k-label { font-weight: 400; color: #889; }

// Code not found

Notice: after many runs the blue ball (weight 10) ends up in the reservoir far more often than the red ball (weight 1). The algorithm never stores the full stream — it only ever holds $k$ items in memory at once.

How does A-Res work?

For each incoming item $i$ with weight $w_i > 0$, compute a key:

$$k_i = u_i^{1/w_i}$$

where $u_i$ is a uniform random number in $(0, 1)$. Keep the $k$ items with the largest keys in a min-heap. When a new item's key exceeds the smallest key in the heap, evict the minimum and insert the newcomer.

Why does this give the right probabilities? The key $u^{1/w}$ is an order statistic trick: raising a uniform random variable to the power $1/w$ produces a distribution that is stochastically larger for bigger $w$. A rigorous proof shows that the probability that item $i$ ends up in the final reservoir of size $k$ is exactly:

$$P(\text{item } i \text{ is selected}) = \frac{w_i \cdot k}{\sum_{j} w_j}$$

(up to boundary effects when $k$ exceeds the stream length).

Complexity:

• Time: $O(n \log k)$ — one heap operation per item, heap size never exceeds $k$.
• Space: $O(k)$ — only the reservoir lives in memory.
• Passes: exactly 1 — each stream item is seen once and then discarded.

Compare to the naive approach: store the entire stream ($O(n)$ space), then do a weighted draw. That works for finite files but fails for infinite or append-only streams. A-Res achieves the same statistical guarantee without ever knowing $n$ in advance.

The algorithm is provably optimal in the information-theoretic sense: any correct weighted reservoir sampler must read each item at least once, so $O(n)$ item-reads is a lower bound. A-Res matches it.

Weighted reservoir sampling is a workhorse of modern data infrastructure:

• Database query optimisation: when a table is too large to scan fully, a weighted sample proportional to row frequency guides the query planner's cost estimates.
• Ad auctions: online advertising platforms select which ads to serve using weighted sampling — ads with higher bids or click-through rates carry larger weights.
• Network traffic monitoring: routers log a weighted random sample of packets (by byte size) to estimate bandwidth distribution without buffering the full traffic log.
• Federated and streaming ML: training data is often an append-only stream; weighted reservoir sampling keeps a representative mini-batch without replaying the stream.
• Monte Carlo simulation: importance sampling — a core variance-reduction technique — is a form of weighted drawing; reservoir variants let it operate on streams.

The algorithm also underpins weighted random forests and sketch data structures used in approximate query processing. Anywhere you need a proportionally fair snapshot of a world that keeps changing, A-Res is the workhorse behind the scenes.

For a complementary view on randomised decision-making under uncertainty, see PAC learning.

Weighted reservoir sampling is one of those algorithms that feels almost too good to be true: give each item a random key $u^{1/w}$, keep the top $k$ in a heap, and you get a statistically perfect proportional sample — from a stream of unknown length, in a single pass, using only $O(k)$ memory.

The insight is elegant: by transforming a uniform random variable with an item's weight, A-Res converts the "bias the draw" problem into a simple sorting problem, one item at a time. The heap handles the rest.

Next time you interact with a recommendation feed, an ad platform, or a dashboard showing "a sample of today's logs," there is a good chance that a weighted reservoir sampler — or a close cousin — is the quiet engine underneath.