Introduction

Every second, internet routers log billions of packets, stock exchanges record millions of trades, and search engines process hundreds of millions of queries. Storing that entire stream is hopeless. Even reading it more than once is often too slow. Yet analysts need to answer questions about the stream: which items dominate? How skewed is the distribution?

The AMS sketch — named after Noga Alon, Yossi Matias and Mario Szegedy, who introduced it in 1996 — solves a central instance of this problem. It estimates the second frequency moment F2=∑ifi2F_2 = \sum_i f_i^2, where fif_i is the number of times item ii appears. F2F_2 captures how concentrated the stream is: a perfectly uniform stream of nn distinct items has F2=nF_2 = n, while a stream dominated by one repeated item has F2≈n2F_2 \approx n^2.

The algorithm needs only a constant number of counters — space logarithmic in the universe size — and makes a single pass through the data. The price is a small probabilistic error, but with high probability the estimate is within a factor of (1±ε)(1 \pm \varepsilon) of the truth.

This was one of the founding results of the field of streaming algorithms, and it earned Alon, Matias and Szegedy the 2005 Gödel Prize.

Try It

Click the letter buttons to add tokens to the stream. Each click sends one item through both the exact counter (which remembers every frequency) and the AMS sketch (which maintains only a few random ±1\pm 1 counters).

<!-- AMS sketch interactive demo — stream tokens and compare exact vs sketch F2 -->
<p class="hint">Click a letter to add it to the stream. The <b>exact F2</b> sums the squared frequencies. The <b>AMS sketch</b> maintains 8 random ±1 counters — each counter's square is an unbiased estimate of F2, and their average converges as the stream grows.</p>
<div class="stream-area">
  <div class="add-btns" id="addBtns">
    <button class="add-btn" data-item="A" type="button">A</button>
    <button class="add-btn" data-item="B" type="button">B</button>
    <button class="add-btn" data-item="C" type="button">C</button>
    <button class="add-btn" data-item="D" type="button">D</button>
    <button class="add-btn" data-item="E" type="button">E</button>
  </div>
  <div class="stream-tokens" id="streamTokens"></div>
</div>
<div class="metrics">
  <div class="metric-box">
    <div class="metric-label">Exact F2</div>
    <div class="metric-value" id="exactF2">0</div>
    <div class="metric-sub" id="freqBreakdown"></div>
  </div>
  <div class="metric-box">
    <div class="metric-label">Sketch estimate</div>
    <div class="metric-value" id="sketchF2">0</div>
    <div class="metric-sub" id="sketchDetail"></div>
  </div>
  <div class="metric-box">
    <div class="metric-label">Relative error</div>
    <div class="metric-value" id="relError">—</div>
  </div>
</div>
<div class="btns">
  <button id="resetBtn" type="button" class="ghost">Reset stream</button>
</div>

/* Styles for the AMS sketch demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.stream-area { margin-bottom: .8rem; }
.add-btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
.add-btn { font: 700 16px ui-monospace, monospace; width: 40px; height: 40px;
           border: 1px solid #1d3557; background: #1d3557; color: #fff;
           border-radius: 8px; cursor: pointer; transition: background .1s; }
.add-btn:hover { background: #2a4a73; }
.stream-tokens { display: flex; flex-wrap: wrap; gap: 3px; min-height: 28px;
                 padding: 4px; background: #f0f4f8; border-radius: 6px;
                 border: 1px solid #d0dae3; }
.token { font: 700 13px ui-monospace, monospace; padding: 2px 6px;
         border-radius: 4px; color: #fff; }
.token-A { background: #1d6fa4; }
.token-B { background: #2a9d5c; }
.token-C { background: #c0533a; }
.token-D { background: #8254a0; }
.token-E { background: #b07d1a; }
.metrics { display: flex; gap: .6rem; flex-wrap: wrap; margin-bottom: .7rem; }
.metric-box { flex: 1; min-width: 100px; background: #f5f8fb; border: 1px solid #d0dae3;
              border-radius: 8px; padding: .5rem .7rem; }
.metric-label { font-size: .75rem; color: #567; text-transform: uppercase; letter-spacing: .05em; margin-bottom: .2rem; }
.metric-value { font: 700 1.5rem ui-monospace, monospace; color: #1d3557; line-height: 1.1; }
.metric-sub { font-size: .72rem; color: #678; margin-top: .25rem; line-height: 1.4; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// AMS sketch for the second frequency moment F2 = sum_i f_i^2
// Core insight: pick random h: item -> {+1,-1}, maintain X = sum h(item) over stream.
// Then E[X^2] = F2. Average k independent X^2 values to reduce variance.

// Build NUM_SKETCHES independent sign-hash tables (each maps items -> +1 or -1).
// A 4-wise independent family suffices in theory; uniform random is fine for a demo.
const NUM_SKETCHES = 8;
const ITEMS = ['A', 'B', 'C', 'D', 'E'];

// Color map for the stream token display — one color per item letter.
const TOKEN_COLORS = { A: '#1d6fa4', B: '#2a9d5c', C: '#c0533a', D: '#8254a0', E: '#b07d1a' };

// Fast deterministic pseudo-random number generator (mulberry32 variant).
function mulberry32(seed) {
  return function() {
    seed |= 0; seed = seed + 0x6D2B79F5 | 0;
    let t = Math.imul(seed ^ seed >>> 15, 1 | seed);
    t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
    return ((t ^ t >>> 14) >>> 0) / 4294967296;
  };
}

// Build one sign-hash table for the given seed.
// Each item gets a uniform random +1 or -1 sign.
function buildHash(seed) {
  const rng = mulberry32(seed);
  const tbl = {};
  for (const item of ITEMS) {
    tbl[item] = rng() < 0.5 ? 1 : -1;
  }
  return tbl;
}

// Pre-build all hash tables once at load time.
const HASHES = Array.from({ length: NUM_SKETCHES }, (_, i) => buildHash(42 + i * 97));

let stream = [];
let freq = {};
// One counter per sketch: X_i = sum of h_i(item) for every streamed item.
let counters = new Array(NUM_SKETCHES).fill(0);

function exactF2() {
  // Exact F2 = sum of squared frequencies — requires remembering all freq counts.
  return Object.values(freq).reduce((s, f) => s + f * f, 0);
}

function sketchEstimate() {
  // Estimate = average of X_i^2 over all sketches (unbiased estimator of F2).
  const sq = counters.map(x => x * x);
  return sq.reduce((a, b) => a + b, 0) / sq.length;
}

function addToken(item) {
  // Update both exact frequencies and all sketch counters on each new token.
  stream.push(item);
  freq[item] = (freq[item] || 0) + 1;
  for (let i = 0; i < NUM_SKETCHES; i++) {
    counters[i] += HASHES[i][item];
  }
  render();
}

function render() {
  // Re-draw the token strip and update all metric boxes.
  const tokensEl = document.getElementById('streamTokens');
  tokensEl.innerHTML = '';
  for (const item of stream) {
    const span = document.createElement('span');
    span.className = 'token token-' + item;
    span.textContent = item;
    tokensEl.appendChild(span);
  }

  const exact = exactF2();
  const estimate = sketchEstimate();

  document.getElementById('exactF2').textContent = exact;
  document.getElementById('sketchF2').textContent = estimate.toFixed(1);

  // Show the per-item frequency breakdown under the exact F2 box.
  const breakdown = Object.entries(freq)
    .sort()
    .map(([k, v]) => k + '=' + v)
    .join(', ');
  document.getElementById('freqBreakdown').textContent =
    stream.length > 0 ? i18nFmt('frequencies: %breakdown%', { breakdown: breakdown }) : '';

  // Show raw counter values under the sketch box.
  const ctrStr = counters.map((x, i) => 'X' + (i + 1) + '=' + x).join(', ');
  document.getElementById('sketchDetail').textContent =
    stream.length > 0 ? i18nFmt('counters: %counters%', { counters: ctrStr }) : '';

  // Relative error = |estimate - exact| / exact (shown as percentage).
  if (exact > 0) {
    const rel = Math.abs(estimate - exact) / exact * 100;
    document.getElementById('relError').textContent = rel.toFixed(1) + '%';
  } else {
    document.getElementById('relError').textContent = '—';
  }
}

function reset() {
  // Clear the stream, frequencies, and all counters back to zero.
  stream = [];
  freq = {};
  counters = new Array(NUM_SKETCHES).fill(0);
  render();
}

document.getElementById('addBtns').addEventListener('click', function(e) {
  const btn = e.target.closest('.add-btn');
  if (btn) addToken(btn.dataset.item);
});
document.getElementById('resetBtn').addEventListener('click', reset);

render();
Result
Console

Notice that the sketch estimate fluctuates — it is a random variable, not a deterministic answer. As you average more independent sketches together, the estimate stabilises (the variance shrinks). This is the same averaging trick behind most randomised approximation algorithms: one trial is noisy, many trials converge.

The Real Complexity

How much does approximating F2F_2 really cost? Precisely:

  • One pass, tiny space. The AMS sketch uses O ⁣(1ε2log⁡1δ)O\!\left(\frac{1}{\varepsilon^2} \log \frac{1}{\delta}\right) words of memory to produce an estimate within (1±ε)(1 \pm \varepsilon) of F2F_2 with probability at least 1−δ1 - \delta. The stream can have any length and the universe any size (apart from a small log⁡\log factor).
  • The core idea. Pick a random sign function h:items→{+1,−1}h : \text{items} \to \{+1, -1\} (a 4-wise independent hash). Maintain the counter X=∑streamh(item)X = \sum_{\text{stream}} h(\text{item}). Then E[X2]=F2\mathbb{E}[X^2] = F_2. One counter gives an unbiased estimate; averaging O(1/ε2)O(1/\varepsilon^2) independent copies reduces variance; taking the median of O(log⁡1/δ)O(\log 1/\delta) groups amplifies confidence.
  • The space lower bound is tight. Alon et al. also proved — using communication-complexity arguments — that any one-pass algorithm approximating F2F_2 within (1±ε)(1 \pm \varepsilon) needs Ω(1/ε2)\Omega(1/\varepsilon^2) bits. So the AMS sketch is optimal up to logarithmic factors.
  • Higher moments are harder. For Fk=∑ifikF_k = \sum_i f_i^k with k>2k > 2, the exponent in the space bound grows: approximating FkF_k requires Ω(n1−2/k)\Omega(n^{1-2/k}) space (Chakrabarti et al., 2003), which can be polynomial in the universe size. Unlike F2F_2, higher moments are genuinely hard in the streaming model.

This combination — a clean algorithm, an essentially matching lower bound, and a precise separation between F2F_2 and higher moments — is what made the paper a landmark in the theory of computation.

Where It Matters

The AMS sketch is not an academic curiosity — it is embedded in real systems that process data at speeds no conventional database could handle:

  • Network traffic analysis: routers compute F2F_2 over packet-destination streams to detect anomalies such as DDoS attacks, where traffic suddenly concentrates on a few IPs.
  • Database query optimisation: query planners use sketch-based F2F_2 estimates to pick join orders without scanning full tables. Systems like PostgreSQL and commercial warehouses have adopted sketch ideas for cardinality and selectivity estimation.
  • Similarity and distance: F2F_2 of the difference vector between two frequency vectors equals the squared Euclidean distance. Sketching that difference in one pass enables fast nearest-neighbour search over streams — the foundation of locality-sensitive hashing.
  • Distinct counting and entropy: variants of the sketch idea underlie HyperLogLog (distinct counts), the Count-Min sketch (point queries), and entropy estimation, each with the same flavour: a tiny randomised summary replaces the full data.

The AMS paper effectively launched the theoretical study of streaming algorithms. Its relatives now appear whenever data arrives faster than storage can absorb it — which, in the modern world, is nearly everywhere. Understanding F2F_2 is the entry point to understanding why randomized algorithms and dimensionality reduction are indispensable tools in large-scale computing.

Conclusion

The AMS sketch carries a striking message: you do not need to remember a data stream to understand it. A few random ±1\pm 1 counters — updated in one pass, occupying a fraction of a kilobyte — can tell you whether the stream is dominated by a handful of heavy-hitters or spread evenly across millions of items. The error is small, the confidence is tunable, and the space usage is provably optimal.

That combination — usefulness, elegance, and a tight lower bound — is what distinguishes a landmark result from a clever trick. The next time you stream video, search the web, or send a packet across the internet, somewhere upstream a sketch like this one is quietly keeping score, using barely any memory at all.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/ams-sketch/Content licensed under CC BY-NC 4.0.