The AMS Sketch

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 $F_2 = \sum_i f_i^2$, where $f_i$ is the number of times item $i$ appears. $F_2$ captures how concentrated the stream is: a perfectly uniform stream of $n$ distinct items has $F_2 = n$, while a stream dominated by one repeated item has $F_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 \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.

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 $\pm 1$ counters).

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</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">{{label_exact}}</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">{{label_sketch}}</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">{{label_error}}</div>
    <div class="metric-value" id="relError">—</div>
  </div>
</div>
<div class="btns">
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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.

How much does approximating $F_2$ really cost? Precisely:

• One pass, tiny space. The AMS sketch uses $O\!\left(\frac{1}{\varepsilon^2} \log \frac{1}{\delta}\right)$ words of memory to produce an estimate within $(1 \pm \varepsilon)$ of $F_2$ with probability at least $1 - \delta$. The stream can have any length and the universe any size (apart from a small $\log$ factor).
• The core idea. Pick a random sign function $h : \text{items} \to \{+1, -1\}$ (a 4-wise independent hash). Maintain the counter $X = \sum_{\text{stream}} h(\text{item})$. Then $\mathbb{E}[X^2] = F_2$. One counter gives an unbiased estimate; averaging $O(1/\varepsilon^2)$ independent copies reduces variance; taking the median of $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 $F_2$ within $(1 \pm \varepsilon)$ needs $\Omega(1/\varepsilon^2)$ bits. So the AMS sketch is optimal up to logarithmic factors.
• Higher moments are harder. For $F_k = \sum_i f_i^k$ with $k > 2$, the exponent in the space bound grows: approximating $F_k$ requires $\Omega(n^{1-2/k})$ space (Chakrabarti et al., 2003), which can be polynomial in the universe size. Unlike $F_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 $F_2$ and higher moments — is what made the paper a landmark in the theory of computation.

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 $F_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 $F_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: $F_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 $F_2$ is the entry point to understanding why randomized algorithms and dimensionality reduction are indispensable tools in large-scale computing.

The AMS sketch carries a striking message: you do not need to remember a data stream to understand it. A few random $\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.