Introduction

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 kk 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.

Try It

Each colored ball in the stream has a weight. A-Res keeps a reservoir of size k=3k = 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.

<!-- Weighted Reservoir Sampling (A-Res) demo: items flow past one by one; -->
<div class="panel">
  <div class="stream-label">Stream</div>
  <div id="stream" class="stream"></div>
  <div class="controls">
    <button id="btn-step" type="button">Step</button>
    <button id="btn-run" type="button">Run full stream</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="reservoir-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">Empirical frequency after many runs <span id="run-count">(0 runs)</span></div>
  <div id="stats" class="stats"></div>
</div>

/* Layout and typography */
* { 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; }
/* Ball styles: colour comes from inline style; classes control opacity and scale. */
.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; }
/* Stats panel: empirical bar chart */
.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; }

/* A-Res: for each item with weight w, compute key = U^(1/w) where U ~ Uniform(0,1). */
/* Keep the k items with the largest keys in a min-heap. One pass, O(k) space. */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Stream items: label, weight, display color. */
const ITEMS = [
  { label: 'A', weight: 1,  color: '#e63946' },
  { label: 'B', weight: 3,  color: '#f4a261' },
  { label: 'C', weight: 5,  color: '#2a9d8f' },
  { label: 'D', weight: 10, color: '#457b9d' },
  { label: 'E', weight: 2,  color: '#8338ec' },
  { label: 'F', weight: 4,  color: '#fb8500' },
  { label: 'G', weight: 6,  color: '#06d6a0' },
];
const K = 3; /* reservoir size */

/* Algorithm state: reservoir array, stream position, run tally. */
let reservoir = [];
let streamIdx = 0;
let runCount = 0;
const tally = {};
ITEMS.forEach(it => { tally[it.label] = 0; });

/* A-Res key: raising a Uniform(0,1) to the power 1/w biases heavier items upward. */
function aresKey(weight) {
  const u = Math.random();
  return Math.pow(u, 1 / weight);
}

/* Process the next stream item. If reservoir not full, add it. Otherwise evict the minimum key if beaten. */
function stepOne() {
  if (streamIdx >= ITEMS.length) return false;
  const item = ITEMS[streamIdx];
  const key = aresKey(item.weight);
  if (reservoir.length < K) {
    reservoir.push({ ...item, key });
  } else {
    const minIdx = reservoir.reduce((mi, e, i) => e.key < reservoir[mi].key ? i : mi, 0);
    if (key > reservoir[minIdx].key) {
      reservoir[minIdx] = { ...item, key };
    }
  }
  streamIdx++;
  return true;
}

/* Render stream balls and reservoir. Colour-code by outcome: selected, rejected, or not-yet-seen. */
function render() {
  const streamEl = document.getElementById('stream');
  streamEl.innerHTML = '';
  ITEMS.forEach((it, i) => {
    const b = document.createElement('div');
    b.className = 'ball' +
      (i < streamIdx
        ? (reservoir.some(r => r.label === it.label) ? ' selected' : ' rejected')
        : (i === streamIdx ? ' current' : ' incoming'));
    b.style.background = it.color;
    b.title = it.label + ' w=' + it.weight;
    b.textContent = it.label;
    streamEl.appendChild(b);
  });

  const resEl = document.getElementById('reservoir');
  resEl.innerHTML = '';
  reservoir.forEach(r => {
    const b = document.createElement('div');
    b.className = 'ball selected';
    b.style.background = r.color;
    b.title = r.label + ' w=' + r.weight + ' key=' + r.key.toFixed(3);
    b.textContent = r.label;
    resEl.appendChild(b);
  });

  const done = streamIdx >= ITEMS.length;
  const statusEl = document.getElementById('status');
  if (!done && streamIdx === 0) {
    statusEl.textContent = 'Press Step or Run full stream to start.';
  } else if (!done) {
    statusEl.textContent = i18nFmt('Processed %label% (weight %weight%) — item %idx% of %total%.', { label: ITEMS[streamIdx - 1].label, weight: ITEMS[streamIdx - 1].weight, idx: streamIdx, total: ITEMS.length });
  } else {
    statusEl.textContent = i18nFmt('Done — %k% items in the reservoir.', { k: K });
  }

  document.getElementById('btn-step').disabled = done;
  document.getElementById('btn-run').disabled = done;
  renderStats();
}

/* Render empirical frequency bars vs. theoretical proportions. */
function renderStats() {
  const statsEl = document.getElementById('stats');
  if (runCount === 0) { statsEl.innerHTML = ''; return; }
  statsEl.innerHTML = '';
  const totalWeight = ITEMS.reduce((s, it) => s + it.weight, 0);
  ITEMS.forEach(it => {
    const empirical = tally[it.label] / runCount;
    const theoretical = (it.weight * K) / totalWeight;
    const pct = Math.round(empirical * 100);
    const thPct = Math.round(theoretical * 100);
    const bar = document.createElement('div');
    bar.className = 'stat-bar';
    bar.innerHTML =
      '<div class="bar-track"><div class="bar-fill" style="height:' + pct + '%;background:' + it.color + '"></div></div>' +
      '<div class="bar-label">' + it.label + '</div>' +
      '<div class="bar-pct">' + pct + '%<br><span style="color:#aaa">~' + thPct + '%</span></div>';
    statsEl.appendChild(bar);
  });
  document.getElementById('run-count').textContent = '(' + runCount + ' runs)';
}

/* Run the full stream in one pass and tally which items ended up in the reservoir. */
function runAll() {
  while (stepOne()) {}
  reservoir.forEach(r => { tally[r.label]++; });
  runCount++;
  render();
}

function resetDemo() {
  reservoir = [];
  streamIdx = 0;
  render();
}

document.getElementById('btn-step').addEventListener('click', () => { stepOne(); render(); });
document.getElementById('btn-run').addEventListener('click', () => { runAll(); });
document.getElementById('btn-reset').addEventListener('click', () => { resetDemo(); });

render();
Result
Console

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 kk items in memory at once.

The Real Complexity

How does A-Res work?

For each incoming item ii with weight wi>0w_i > 0, compute a key:

ki=ui1/wik_i = u_i^{1/w_i}

where uiu_i is a uniform random number in (0,1)(0, 1). Keep the kk 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 u1/wu^{1/w} is an order statistic trick: raising a uniform random variable to the power 1/w1/w produces a distribution that is stochastically larger for bigger ww. A rigorous proof shows that the probability that item ii ends up in the final reservoir of size kk is exactly:

P(item i is selected)=wi⋅k∑jwjP(\text{item } i \text{ is selected}) = \frac{w_i \cdot k}{\sum_{j} w_j}

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

Complexity:

  • Time: O(nlog⁡k)O(n \log k) — one heap operation per item, heap size never exceeds kk.
  • Space: O(k)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)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 nn 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)O(n) item-reads is a lower bound. A-Res matches it.

Where It Matters

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.

Conclusion

Weighted reservoir sampling is one of those algorithms that feels almost too good to be true: give each item a random key u1/wu^{1/w}, keep the top kk 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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/weighted-reservoir-sampling/Content licensed under CC BY-NC 4.0.