---
title: Streaming Sketches
module: Data Structures
moduleNumber: 4
lessonNumber: 12
order: 412
summary: |
  Sampling and counting kept a random subset or a single approximate tally.
  Sketches go further: fixed, tiny summaries that answer questions about a
  stream's frequencies. We meet the Count–Min sketch for point frequency
  estimation, Misra–Gries for heavy hitters, and HyperLogLog for distinct
  counts, each trading a controlled error for space that never grows with the
  stream.
topics: [Streaming Algorithms, Hashing]
sources:
  - book: CLRS
    ref: "App. C — Probability; Ch. 11 — Hashing"
  - book: Skiena
    ref: "§3.7 — Hashing"
  - book: Erickson
    ref: "Ch. — Randomized Algorithms"
practice:
  - title: 'Find Median from Data Stream'
    slug: find-median-from-data-stream
    difficulty: Hard
  - title: 'Kth Largest Element in a Stream'
    slug: kth-largest-element-in-a-stream
    difficulty: Easy
  - title: 'Top K Frequent Elements'
    slug: top-k-frequent-elements
    difficulty: Medium
  - title: 'First Unique Character in a String'
    slug: first-unique-character-in-a-string
    difficulty: Easy
---

This builds on [Data-Stream Algorithms](/algorithms/data-structures/data-stream-algorithms),
which set up the streaming model and its exactness-for-space trade-off, then
applied it to two problems: keeping a uniform sample with reservoir sampling,
and keeping an approximate count with Morris counting. Both summarized the stream
as a whole. This lesson asks harder questions about the _contents_ of the stream,
how often a given item occurred, which items are frequent, and how many distinct
items there were, and answers each with a **sketch**: a small array of counters,
updated by hashing, whose size is fixed in advance and never grows with the
stream. As before the tools are hashing and randomized analysis, and as before
the answers are approximate, with an error set by choosing the sketch's
dimensions.

## Count–Min sketch: frequency estimation in a grid

**Problem.** Over a stream of items drawn from a huge universe, estimate the
frequency $f_a$ of any queried item $a$ using space far smaller than the number
of distinct items.

**Idea.** Keep a small grid of counters with $d$ rows and $w$ columns. Equip each
row $r$ with its own hash function $h_r$ mapping items into $[1, w]$. To record an
item, bump one counter per row, the cell its row's hash selects. Collisions only
ever _add_ to a counter, so each row gives an **overestimate** of the true
frequency; taking the **minimum across the $d$ rows** keeps the tightest one.

$$
% caption: A Count–Min sketch with $d = 3$ rows and $w = 6$ columns. Each row's hash sends item
%          $a$ to one column ($h_1(a) = 3$, $h_2(a) = 5$, $h_3(a) = 2$ here), and that cell is
%          incremented. A query returns $\hat f_a = \min_r C[r][h_r(a)]$, the smallest of the
%          $d$ row estimates, since every row overcounts.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=8mm, minimum height=7mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \definecolor{red}{HTML}{D1342B}
  % grid 3 x 6
  \foreach \r in {0,1,2} {
    \foreach \c in {0,...,5} {
      \node[cell] (g\r-\c) at (\c*0.9, -\r*0.85) {};
    }
  }
  % hashed cells for item a: one per row, different columns
  \node[cell, fill=acc!20, draw=acc, thick] at (1.8,0)     {$5$};
  \node[cell, fill=acc!20, draw=acc, thick] at (3.6,-0.85) {$4$};
  \node[cell, fill=red!18,  draw=red,  thick] at (0.9,-1.7) {$9$};
  % hash labels, one per row, left of the grid
  \node[acc, font=\scriptsize, anchor=east] (l1) at (-0.85,0)     {$h_1(a)$ = 3};
  \node[acc, font=\scriptsize, anchor=east] (l2) at (-0.85,-0.85) {$h_2(a)$ = 5};
  \node[acc, font=\scriptsize, anchor=east] (l3) at (-0.85,-1.7)  {$h_3(a)$ = 2};
  % item entering from the left; arrows fan to the hash labels, outside the grid
  \node[green, font=\footnotesize\bfseries] (a) at (-3.9,-0.85) {item $a$};
  \draw[acc, ->] (a.east) to[bend left=12]  (l1.west);
  \draw[acc, ->] (a.east) -- (l2.west);
  \draw[acc, ->] (a.east) to[bend right=12] (l3.west);
  % min readout
  \node[align=left, font=\scriptsize, anchor=west] at (6.3,-0.85)
    {query $a$\\[1mm] tak\/e $\min$ over rows\\[1mm] {\color{green}$\hat f_a = 4$}\\[1mm] {\color{red}row $3$ overcoun\/ts}};
  \draw[green, ->] (4.95,-0.85) -- (6.15,-0.85);
\end{tikzpicture}
$$

The update and query are both a handful of hashes; the whole structure is one
$d \times w$ array of integers.

```algorithm
caption: Count–Min sketch — $\textsc{Update}$ and $\textsc{Query}$
number: 3
procedure $\textsc{Update}(a)$ // record one occurrence of item $a$
  for $r \gets 1$ to $d$ do
    $C[r][\,h_r(a)\,] \gets C[r][\,h_r(a)\,] + 1$ // bump one cell per row
procedure $\textsc{Query}(a)$ // estimate the frequency of $a$
  $\hat f \gets +\infty$
  for $r \gets 1$ to $d$ do
    $\hat f \gets \min\parens{\hat f,\; C[r][\,h_r(a)\,]}$ // tightest row wins
  return $\hat f$
```

**A worked trace.** Take a tiny sketch with $d = 2$ rows and $w = 4$ columns,
and hash functions given by the table
$$
h_1:\; a \mapsto 2,\; b \mapsto 1,\; c \mapsto 2,\; d \mapsto 4,
\qquad
h_2:\; a \mapsto 3,\; b \mapsto 1,\; c \mapsto 1,\; d \mapsto 2.
$$
Feed it the ten-item stream $a\,b\,a\,c\,b\,a\,a\,c\,d\,b$, so the true
frequencies are $f_a = 4$, $f_b = 3$, $f_c = 2$, $f_d = 1$. Each arrival bumps
cell $h_1(\cdot)$ in row $1$ and cell $h_2(\cdot)$ in row $2$. Row $1$
accumulates $b$'s three occurrences in column $1$, $a$'s four plus $c$'s two in
the shared column $2$, and $d$'s single occurrence in column $4$. Row $2$ piles
$b$ and $c$ together in column $1$, puts $d$ in column $2$, and keeps $a$ alone
in column $3$.

$$
% caption: Count–Min state ($d = 2$, $w = 4$) after the stream $a\,b\,a\,c\,b\,a\,a\,c\,d\,b$
%          with the hash table above. Querying $a$ reads cells $6$ and $4$; the min, $4$, is
%          exact because row $2$ kept $a$ collision-free. Querying $c$ reads $6$ and $5$, both
%          inflated by collisions, and returns $5$ against a true count of $2$.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=9mm, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \definecolor{red}{HTML}{D1342B}
  % column headers
  \foreach \c in {0,...,3} {
    \node[black, font=\scriptsize] at (\c*1.0, 0.8) {\the\numexpr\c+1\relax};
  }
  % row 1
  \node[acc, font=\scriptsize, anchor=east] at (-0.75,0) {$h_1$};
  \node[cell] at (0,0) {$3$};
  \node[cell, fill=red!14, draw=red, thick] at (1.0,0) {$6$};
  \node[cell] at (2.0,0) {$0$};
  \node[cell] at (3.0,0) {$1$};
  % contributors under row 1
  \node[black, font=\scriptsize] at (0,-0.75) {$b$};
  \node[black, font=\scriptsize] at (1.0,-0.75) {$a$ + $c$};
  \node[black, font=\scriptsize] at (3.0,-0.75) {$d$};
  % row 2
  \node[acc, font=\scriptsize, anchor=east] at (-0.75,-1.7) {$h_2$};
  \node[cell, fill=red!14, draw=red, thick] at (0,-1.7) {$5$};
  \node[cell] at (1.0,-1.7) {$1$};
  \node[cell, fill=green!16, draw=green, thick] at (2.0,-1.7) {$4$};
  \node[cell] at (3.0,-1.7) {$0$};
  % contributors under row 2
  \node[black, font=\scriptsize] at (0,-2.45) {$b$ + $c$};
  \node[black, font=\scriptsize] at (1.0,-2.45) {$d$};
  \node[black, font=\scriptsize] at (2.0,-2.45) {$a$};
  % readout
  \node[align=left, font=\scriptsize, anchor=west] at (5.0,-0.4)
    {query $a$: rows read 6, 4\\[0.5mm] {\color{green}min = 4, exact}};
  \node[align=left, font=\scriptsize, anchor=west] at (5.0,-1.6)
    {query $c$: rows read 6, 5\\[0.5mm] {\color{red}min = 5, true coun{}t 2}};
\end{tikzpicture}
$$

The two queries show both cases. Row $2$ happened to give $a$ a private cell, so
the minimum returns the exact count $4$. Item $c$ shares a cell with $a$ in
row $1$ and with $b$ in
row $2$, so both estimates are inflated and even the minimum, $5$, is more than
double the true count $2$. This is the general pattern: heavy items
are estimated well because their own mass dominates their cells, while rare
items are swamped by whatever collides with them.

Why take the minimum: every row's counter for $a$ equals $a$'s true
count _plus_ whatever other items collided into the same cell. Collisions never
subtract, so $C[r][h_r(a)] \ge f_a$ always, and the minimum is the row with the
least colliding mass.

> **Theorem (Count–Min error).** With $w = \lceil e/\varepsilon\rceil$ columns and
> $d = \lceil \ln(1/\delta)\rceil$ rows, the estimate satisfies $\hat f_a \ge f_a$
> always, and with probability at least $1 - \delta$,
> $$
> \hat f_a \;\le\; f_a + \varepsilon\,\lVert f\rVert_1,
> $$
> where $\lVert f\rVert_1$ is the total stream length. The space is
> $O(\varepsilon^{-1}\log(1/\delta))$ counters.

> **Proof.** Fix a row $r$ and let the **excess** be the collision mass
> $$
> Z_r \;=\; C[r][h_r(a)] - f_a \;=\; \sum_{b \ne a} f_b\,\big[\,h_r(b)=h_r(a)\,\big]
> \;\ge\; 0.
> $$
> Under a pairwise-independent hash into $w$ cells, each other item lands on
> $a$'s cell with probability $1/w$, so by linearity of expectation
> $$
> \mathbb{E}[Z_r] \;=\; \sum_{b \ne a} \frac{f_b}{w}
> \;\le\; \frac{\lVert f\rVert_1}{w}
> \;\le\; \frac{\varepsilon\,\lVert f\rVert_1}{e}.
> $$
> $Z_r$ is nonnegative, so Markov's inequality applies:
> $$
> \Pr\big[\,Z_r > \varepsilon\,\lVert f\rVert_1\,\big]
> \;\le\; \frac{\mathbb{E}[Z_r]}{\varepsilon\,\lVert f\rVert_1}
> \;\le\; \frac{1}{e}.
> $$
> The $d$ rows use independent hashes, so the events are independent, and the
> minimum exceeds $f_a + \varepsilon\lVert f\rVert_1$ only if _every_ row does:
> $$
> \Pr\big[\hat f_a > f_a + \varepsilon\lVert f\rVert_1\big]
> \;\le\; \left(\frac{1}{e}\right)^{d}
> \;=\; e^{-d} \;\le\; e^{-\ln(1/\delta)} \;=\; \delta. \qquad\qed
> $$
> [^clrs-prob]

**Choosing the grid.** The parameters translate directly into memory. For a
$0.1\%$ additive error ($\varepsilon = 0.001$) with $99\%$ confidence
($\delta = 0.01$): $w = \lceil e/0.001 \rceil = 2719$ columns and
$d = \lceil \ln 100 \rceil = 5$ rows, about $13{,}600$ counters, some $54$ KB of
$4$-byte cells. That footprint is fixed no matter whether the stream carries
thousands of items or trillions, and no matter how many distinct items appear;
only the guarantee's noise floor $\varepsilon\lVert f\rVert_1$ scales with the
stream.

The error is **one-sided** (always an overestimate) and **additive** in the
stream length, so Count–Min is most accurate for the frequent items whose true
counts dwarf the $\varepsilon\,\lVert f\rVert_1$ noise floor, exactly the items
one usually cares about. Two practical footnotes. First, the sketch answers
_point queries_ only: it cannot list the frequent items by itself, because the
universe is too large to query exhaustively; pair it with a heap of the
top candidates seen so far, or with Misra–Gries below, when you need the list.
Second, a small tweak called **conservative update** increments, on each
arrival, only those of the item's $d$ counters that equal the current minimum;
every row still upper-bounds the truth, and collisions inflate the cells more
slowly. Count–Min is used in network flow monitoring, trending-term counts, and
database query-frequency statistics.

::impl{algo="count_min_sketch"}

## Misra–Gries: heavy hitters in $O(1/\varepsilon)$ counters

**Problem.** Find the **heavy hitters**, every item whose frequency exceeds an
$\varepsilon$ fraction of the stream, without storing all distinct items.

**Idea.** Keep at most $k - 1$ labelled counters, where $k = \lceil 1/\varepsilon
\rceil$. For each arriving item: if it already holds a counter, increment it; if a
counter is free, claim it at $1$; otherwise **decrement every counter**, dropping
any that hit zero. The decrement pairs occurrences off: each new unmatched item
cancels one occurrence of $k - 1$ others, so an item can keep a counter only if
it appeared often enough to absorb the cancellations.

```algorithm
caption: $\textsc{MisraGries}(\text{stream}, k)$ — heavy-hitter candidates in $k - 1$ counters
number: 4
$T \gets$ empty map // at most $k - 1$ labelled counters
for each item $x$ do
  if $x \in T$ then
    $T[x] \gets T[x] + 1$ // $x$ already holds a counter
  else if $|T| < k - 1$ then
    $T[x] \gets 1$ // a counter is free: claim it
  else // table full, $x$ unmatched: decrement round
    for each label $y$ in $T$ do
      $T[y] \gets T[y] - 1$
      if $T[y] = 0$ then remove $y$ from $T$ // evict at zero
return $T$ // candidates with estimates $\hat f_y = T[y]$
```

$$
% caption: The two cases of Misra–Gries with $k - 1 = 3$ counters, from the same state. Seeing
%          $a$, which holds a counter, increments it. Seeing $z$, unmatched with the table full,
%          decrements every counter instead; $c$ hits zero and is evicted. $z$ itself is not
%          stored — its one occurrence cancels against one occurrence of each label.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  ctr/.style={draw, minimum width=11mm, minimum height=8mm, inner sep=1pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \definecolor{red}{HTML}{D1342B}
  % state before (top, centered)
  \node[black, font=\scriptsize] at (4.0,1.1) {coun{}ters};
  \node[ctr, fill=acc!10] (c1) at (2.4,0.3) {$a$ : 4};
  \node[ctr, fill=acc!10] (c2) at (4.0,0.3) {$b$ : 2};
  \node[ctr, fill=acc!10] (c3) at (5.6,0.3) {$c$ : 1};
  % case A: see a (bottom left)
  \node[ctr, fill=green!14, draw=green, thick] (a1) at (-0.8,-2.4) {$a$ : 5};
  \node[ctr, fill=acc!10] (a2) at (0.8,-2.4) {$b$ : 2};
  \node[ctr, fill=acc!10] (a3) at (2.4,-2.4) {$c$ : 1};
  \node[green, font=\scriptsize] at (0.8,-3.3) {after seeing $a$};
  \draw[green, ->, thick] (c1.south) to[bend right=18] (a1.north);
  \node[green, font=\scriptsize, anchor=east] at (0.35,-1.2) {see $a$: incremen\/t};
  % case B: see z (bottom right)
  \node[ctr, fill=acc!10] (b1) at (5.6,-2.4) {$a$ : 3};
  \node[ctr, fill=acc!10] (b2) at (7.2,-2.4) {$b$ : 1};
  \node[ctr, fill=red!10, draw=red] (b3) at (8.8,-2.4) {$c$ : 0};
  \node[red, font=\scriptsize] at (6.7,-3.3) {after seeing $z$};
  \draw[red, ->, thick] (c3.south) to[bend left=18] (b3.north);
  \node[red, font=\scriptsize, anchor=west] at (7.9,-1.2) {see $z$ (new, full):};
  \node[red, font=\scriptsize, anchor=west] at (7.9,-1.6) {decremen\/t all};
  \node[red, font=\scriptsize] at (8.8,-3.3) {evicted};
\end{tikzpicture}
$$

**A worked trace.** Run Misra–Gries with $k - 1 = 2$ counters
($k = 3$, so $\varepsilon = 1/3$) on the seven-item stream
$a\,b\,a\,c\,a\,b\,a$, where $f_a = 4$, $f_b = 2$, $f_c = 1$.

1. **$a$** — table empty, claim a counter: $\{a{:}1\}$.
2. **$b$** — one counter free, claim it: $\{a{:}1,\; b{:}1\}$.
3. **$a$** — matched, increment: $\{a{:}2,\; b{:}1\}$.
4. **$c$** — unmatched, table full: decrement all. $a$ drops to $1$, $b$ drops
   to $0$ and is evicted; $c$ itself is not stored: $\{a{:}1\}$.
5. **$a$** — matched, increment: $\{a{:}2\}$.
6. **$b$** — counter free again, claim it: $\{a{:}2,\; b{:}1\}$.
7. **$a$** — matched, increment: $\{a{:}3\}$, with $b{:}1$ alongside.

$$
% caption: Misra–Gries with $k - 1 = 2$ counters on $a\,b\,a\,c\,a\,b\,a$. Each column shows
%          the arriving item and the counter table after processing it. Step 4 is the one
%          decrement round: $c$ arrives unmatched with the table full, so both counters drop
%          and $b$ is evicted. The final estimate $a{:}3$ under-reports $f_a = 4$ by exactly
%          that one round, within the bound $\lfloor n/k \rfloor = \lfloor 7/3 \rfloor = 2$.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  itm/.style={draw, minimum width=7mm, minimum height=7mm, inner sep=1pt},
  ctr/.style={draw, minimum width=10mm, minimum height=7mm, inner sep=1pt},
  emp/.style={draw=black, minimum width=10mm, minimum height=7mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \definecolor{red}{HTML}{D1342B}
  % step numbers
  \foreach \s in {1,...,7} {
    \node[black, font=\scriptsize] at (\s*1.4-1.4, 1.5) {\s};
  }
  % arriving items
  \node[itm, fill=green!14, draw=green] (i1) at (0,0.7)   {$a$};
  \node[itm, fill=green!14, draw=green] (i2) at (1.4,0.7) {$b$};
  \node[itm, fill=green!14, draw=green] (i3) at (2.8,0.7) {$a$};
  \node[itm, fill=red!14, draw=red, thick] (i4) at (4.2,0.7) {$c$};
  \node[itm, fill=green!14, draw=green] (i5) at (5.6,0.7) {$a$};
  \node[itm, fill=green!14, draw=green] (i6) at (7.0,0.7) {$b$};
  \node[itm, fill=green!14, draw=green] (i7) at (8.4,0.7) {$a$};
  % down arrows from item to table
  \foreach \s in {1,...,7} {
    \draw[black, ->] (\s*1.4-1.4, 0.32) -- (\s*1.4-1.4, -0.12);
  }
  % counter slot 1 (top row of table)
  \node[ctr, fill=acc!10] at (0,-0.5)   {$a$ : 1};
  \node[ctr, fill=acc!10] at (1.4,-0.5) {$a$ : 1};
  \node[ctr, fill=acc!10] at (2.8,-0.5) {$a$ : 2};
  \node[ctr, fill=red!10, draw=red] at (4.2,-0.5) {$a$ : 1};
  \node[ctr, fill=acc!10] at (5.6,-0.5) {$a$ : 2};
  \node[ctr, fill=acc!10] at (7.0,-0.5) {$a$ : 2};
  \node[ctr, fill=acc!10] at (8.4,-0.5) {$a$ : 3};
  % counter slot 2 (bottom row of table)
  \node[emp] at (0,-1.3) {};
  \node[ctr, fill=acc!10] at (1.4,-1.3) {$b$ : 1};
  \node[ctr, fill=acc!10] at (2.8,-1.3) {$b$ : 1};
  \node[emp] at (4.2,-1.3) {};
  \node[emp] at (5.6,-1.3) {};
  \node[ctr, fill=acc!10] at (7.0,-1.3) {$b$ : 1};
  \node[ctr, fill=acc!10] at (8.4,-1.3) {$b$ : 1};
  % decrement annotation under step 4
  \node[red, font=\scriptsize, align=center] at (4.2,-2.2)
    {decremen\/t all\\ $b$ evicted};
\end{tikzpicture}
$$

The final table reports $\hat f_a = 3$ and $\hat f_b = 1$ against the truth
$f_a = 4$, $f_b = 2$. Both are under-reported by exactly $1$, the number of
decrement rounds, and the theorem below says that number can never exceed
$n/k$. The heavy hitter $a$ (frequency $4 > \varepsilon n = 7/3$) survived, as
it must; $b$ survived too, a false positive the guarantee permits.

Each surviving counter under-reports by at most the number of decrement rounds,
which is bounded because each round consumes $k$ distinct arrivals.

> **Theorem (Misra–Gries guarantee).** Using $k - 1$ counters with $k =
> \lceil 1/\varepsilon\rceil$, the stored count $\hat f_a$ of any item satisfies
> $$
> f_a - \varepsilon n \;\le\; \hat f_a \;\le\; f_a,
> $$
> so every true heavy hitter (with $f_a > \varepsilon n$) is retained, with no
> false negatives among them. The space is $O(1/\varepsilon)$.

> **Proof.** $\hat f_a \le f_a$ since counters only rise on a genuine occurrence
> of $a$. For the lower bound, charge each decrement round its cost in stream
> items: the round is triggered by one arrival (the unmatched new item, which is
> discarded) and removes one counted occurrence from each of the $k - 1$ labels,
> so it consumes $k$ distinct stream positions, and no position is charged twice.
> A stream of length $n$ therefore admits at most $n/k \le \varepsilon n$
> decrement rounds. Item $a$'s counter loses at most one per round, so it ends at
> least $f_a - \varepsilon n$. (If $a$ never held a counter at some point it
> "should" have, that absence is itself accounted by the same rounds.) $\qed$

**From candidates to answers.** The guarantee runs one way: no false negatives
among the true heavy hitters, but false positives are possible, as $b$ in the
trace shows. When exact confirmation matters and the data can be replayed, a
second pass over the stream counts only the $O(1/\varepsilon)$ surviving
candidates exactly. In a strict one-pass setting, a Count–Min sketch running
alongside serves as the verifier: Misra–Gries produces the candidates, Count–Min
estimates their counts. The two sketches are complementary in their bias as well,
Misra–Gries never overestimates and Count–Min never underestimates, so together
they bracket the truth.

The special case $k = 2$ is the classic **majority vote** algorithm: one counter,
incremented on a match, decremented on a mismatch, and whatever survives is the
only possible majority element. Misra–Gries is the general-$k$ version of that
pairing-off argument, and the standard answer to _find the trending hashtags /
the top talkers on a link_.

::impl{algo="misra_gries"}

## HyperLogLog: counting the distinct

**Problem.** Estimate the number of **distinct** items in a stream, the
cardinality, in a few kilobytes, even when there are billions of distinct values.

Storing a set or a hash table to deduplicate would cost $\Omega(\text{distinct})$
space, exactly what we cannot afford. **HyperLogLog** instead reads cardinality
off a statistic that is invariant to duplicates: the longest run of leading zeros
seen among the items' hash values.

**Idea.** Hash each item to a uniform bit string and look at the position of its
first $1$ bit, equivalently the number of leading zeros, $\rho$. A leading run of
$\rho$ zeros occurs with probability $2^{-\rho}$, so seeing a maximum run of
length $R$ across the stream suggests roughly $2^{R}$ distinct values were hashed,
duplicates don't matter, since a repeated item hashes to the same string and
contributes no new zeros.

$$
% caption: HyperLogLog reads cardinality from the maximum leading-zero count. A hash with $R$
%          leading zeros appears about once per $2^{R}$ distinct items, so the largest observed
%          $R$ estimates $\log_2$ of the cardinality. Buckets average many such estimates to
%          shrink the variance.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  bit/.style={draw, minimum width=5.5mm, minimum height=5.5mm, inner sep=0, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % hash string 0 0 0 1 ... with leading zeros highlighted
  \foreach \v [count=\i from 0] in {0,0,0,1,0,1,1,0} {
    \ifnum\i<3
      \node[bit, fill=acc!18, draw=acc] (h\i) at (\i*0.62,0) {$\v$};
    \else
      \node[bit] (h\i) at (\i*0.62,0) {$\v$};
    \fi
  }
  \node[font=\scriptsize] at (-1.2,0) {hash};
  % brace-style underline for leading zeros (well below the cell row)
  \draw[acc, thick] (-0.27,-0.95) -- (1.55,-0.95);
  \draw[acc] (-0.27,-0.95) -- (-0.27,-0.8);
  \draw[acc] (1.55,-0.95) -- (1.55,-0.8);
  \node[acc, font=\scriptsize] at (0.64,-1.35) {$R = 3$ leading zeros};
  % estimate
  \node[green, font=\footnotesize\bfseries, align=center] at (6.6,0)
    {estimate ab\/out\\ $2^{R}$ distinct};
  \draw[green, ->] (4.85,0) -- (5.45,0);
\end{tikzpicture}
$$

A single max-zero count is far too noisy, its variance is enormous: one
unluckily long run of zeros, from a single hash value, doubles or quadruples the
estimate, and more stream data cannot correct it, because the maximum never
decreases. The repair has two parts.

**Buckets and the harmonic mean.** Split the sketch into $m = 2^{b}$ **buckets**
and give each bucket its own maximum. One hash serves both roles:
the first $b$ bits of $h(x)$ choose the bucket $j$, and the remaining bits
supply the statistic $\rho(x)$, the position of the first $1$ bit (one more
than the count of leading zeros). Each bucket keeps a small register
$M[j] = \max \rho$ over the items routed to it, so the sketch as a whole is $m$
independent estimates produced by a single pass and a single hash per item.

```algorithm
caption: $\textsc{HyperLogLog}(\text{stream}, m = 2^{b})$ — distinct-count estimation
number: 5
$M[1 \dots m] \gets 0$ // one register per bucket
for each item $x$ do
  $u \gets h(x)$ // uniform bit string
  $j \gets 1 + \text{int}(u_1 u_2 \dots u_b)$ // first $b$ bits pick a bucket
  $\rho \gets$ position of first $1$ bit in $u_{b+1} u_{b+2} \dots$
  $M[j] \gets \max\parens{M[j],\; \rho}$ // registers only ever grow
return $\hat n \gets \alpha_m \, m^2 \Big/ \sum_{j=1}^{m} 2^{-M[j]}$ // harmonic combination
```

The estimator combines the registers by a **harmonic mean**: the raw estimate is
$$
\hat n \;=\; \alpha_m\, m \cdot
\underbrace{\frac{m}{\sum_{j=1}^{m} 2^{-M[j]}}}_{\text{harmonic mean of } 2^{M[j]}},
$$
where $\alpha_m$ is a bias-correction constant that tends to
$1/(2\ln 2) \approx 0.7213$ as $m$ grows. The harmonic mean is the right
average precisely because of the outlier problem: each $2^{M[j]}$ is a
per-bucket cardinality guess whose distribution has a heavy upper tail, and an
arithmetic mean would let one outlier register drag the whole estimate up. The
harmonic mean works on reciprocals, where an outlier contributes a term
near zero instead of a huge one, so single outliers are damped rather than
amplified. Averaging across the $m$ buckets then shrinks the relative standard
error to about $1.04/\sqrt{m}$.

**A small example.** With $m = 4$ buckets (far too few in practice, the right
size for arithmetic by hand), suppose a run leaves the registers at
$M = [2, 3, 1, 2]$. Then
$$
\sum_j 2^{-M[j]} = \tfrac14 + \tfrac18 + \tfrac12 + \tfrac14 = \tfrac98,
\qquad
\hat n = \alpha_4 \cdot \frac{4^2}{9/8} = \alpha_4 \cdot \frac{128}{9}
\approx 0.7 \times 14.2 \approx 10,
$$
a sensible reading for a run in which roughly a dozen distinct values were
hashed. Each register only needed to store a number no larger than the hash
length, so $5$ to $6$ bits per bucket suffice for $64$-bit hashes.

**Range corrections.** Two regimes need care. When the true cardinality is small
compared to $m$, many buckets are still empty ($M[j] = 0$) and the raw formula
biases high; the fix is to count the $V$ empty buckets and switch to the
**linear counting** estimate $\hat n = m \ln(m/V)$, which reads cardinality off
the emptiness rate instead. At the far top of the range, hash collisions in a
$32$-bit hash space compress the estimate, which either a correction term or,
in modern implementations, a $64$-bit hash makes moot.

> **Guarantee.** With $m$ buckets, HyperLogLog estimates the cardinality with
> relative standard error $\approx 1.04/\sqrt{m}$, using $O(m\log\log n)$ bits.
> Concretely, $m = 2^{11} = 2048$ buckets of $6$ bits give about $2.3\%$ error
> in $1.5$ KB, regardless of whether the true count is thousands or billions.

This is the structure behind `COUNT(DISTINCT ...)` approximations in analytics
databases and unique-visitor counts at web scale: a fixed, tiny footprint that
counts distinct items without storing them.
The register semantics also make the sketch mergeable: since registers only take
maxima, two HyperLogLog sketches built on different machines merge by a
pointwise $\max$, giving the sketch of the combined stream — which is why it
distributes so well.

::impl{algo="hyperloglog"}
## Sketches in the wild

All three sketches run in production at scale, and each has later refinements
worth knowing.

The **Count–Min sketch** is due to Cormode and Muthukrishnan (2005), and its
_conservative update_ variant, incrementing on each arrival only the counters
that currently equal the item's minimum, comes from Estan and Varghese's
network-measurement work. Databases use it and its relatives for query
planning: Apache Spark, for instance, exposes `CountMinSketch` directly, and the
same idea underlies the frequency statistics a query optimizer keeps to guess
join selectivities. A close cousin, the **count sketch** of Charikar, Chen, and
Farach-Colton (2002), hashes each item to $\pm 1$ as well as to a bucket, which
makes its estimate _unbiased_ rather than one-sided, useful when frequencies
must be summed and subtracted.

**Misra–Gries** (1982) is the ancestor of the two heavy-hitter algorithms most
deployed today, **Space-Saving** (Metwally, Agrawal, El Abbadi, 2005) and
**Lossy Counting** (Manku and Motwani, 2002). Space-Saving keeps the same
$O(1/\varepsilon)$ counters but, instead of decrementing everyone on an
overflow, overwrites the current minimum counter with the new item and inherits
its count, which tends to track the true frequencies more tightly. These power
the "trending now" and "top talkers" panels of large systems where storing
per-item state is out of the question.

**HyperLogLog** (Flajolet, Fusy, Gandouet, Meunier, 2007) refined Durand and
Flajolet's LogLog, which itself descended from the Flajolet–Martin sketch of
1985. The practically important sequel is Google's **HyperLogLog++** (Heule,
Nunkesser, Hall, 2013), which adds a 64-bit hash, a bias-corrected small-range
estimate, and a sparse representation for low cardinalities; it is what backs
`APPROX_COUNT_DISTINCT` in BigQuery and the `PFCOUNT` command in Redis. The
mergeability that makes HyperLogLog distribute, two sketches combine by a
pointwise maximum, is what lets these systems shard a cardinality count
across machines and recombine the pieces exactly.[^btb-sketches]

## Where these sketches live, and the takeaway

Each sketch answers a different question about a stream's contents, and the
choice among them starts from the question:

| question about the stream    | technique          | space                                        | guarantee                                                     |
| ---------------------------- | ------------------ | -------------------------------------------- | ------------------------------------------------------------- |
| how often did item $a$ occur? | Count–Min sketch   | $O(\varepsilon^{-1}\log(1/\delta))$ counters | $f_a \le \hat f_a \le f_a + \varepsilon n$ w.p. $1-\delta$    |
| which items are frequent?    | Misra–Gries        | $O(1/\varepsilon)$ counters                  | $f_a - \varepsilon n \le \hat f_a \le f_a$, deterministic     |
| how many distinct items?     | HyperLogLog        | $O(m \log\log n)$ bits                       | relative error $\approx 1.04/\sqrt{m}$                        |

Two contrasts in that table matter. Misra–Gries is the only
**deterministic** guarantee, no hashing, no failure probability, but it answers
only "who is frequent," while Count–Min answers arbitrary point queries at the
price of randomness. And the two frequency sketches err in opposite directions,
under versus over: Misra–Gries never overestimates and Count–Min never
underestimates, so running both **brackets** the truth, a standard move when you
need a two-sided guarantee from one-sided tools.

All three share the pattern from Morris counting in the previous lesson:
a small random summary standing in for a quantity too large to store exactly,
made accurate by structure — averaging across rows in Count–Min,
cancellation in Misra–Gries, harmonic averaging across buckets in HyperLogLog.
Databases keep Count–Min and HyperLogLog statistics to plan queries
without scanning whole tables; routers run Misra–Gries and Count–Min to spot
heavy flows at line rate; analytics pipelines use HyperLogLog for
unique-visitor counts over unbounded clickstreams. Each fixes its footprint in
advance and accepts a small, tunable error in return.

## Takeaways

- A **sketch** is a fixed-size summary of a stream, updated by hashing, whose
  space is chosen in advance and never grows with the stream; the price is an
  approximate, usually probabilistic, answer.
- The **Count–Min sketch** estimates frequencies in a $d \times w$ counter grid;
  its error is one-sided ($\hat f_a \ge f_a$) and additive,
  $\hat f_a \le f_a + \varepsilon\lVert f\rVert_1$ with probability $1-\delta$,
  by a Markov-plus-independence argument across rows. It is most accurate for the
  heavy items whose own mass dominates their cells.
- **Misra–Gries** finds heavy-hitter candidates in $O(1/\varepsilon)$ counters
  with the deterministic sandwich $f_a - \varepsilon n \le \hat f_a \le f_a$;
  each decrement round consumes $k$ stream items, so there are at most $n/k$
  rounds. The case $k = 2$ is the classic majority-vote algorithm.
- **HyperLogLog** estimates distinct counts from per-bucket maximum leading-zero
  statistics combined by a harmonic mean, with relative error
  $\approx 1.04/\sqrt{m}$ in a few kilobytes, and merges across machines by a
  pointwise $\max$.
- The two frequency sketches err in opposite directions, so running both brackets
  the truth; Misra–Gries alone is the only fully deterministic guarantee of the
  three.

[^clrs-prob]: **CLRS**, App. C — Counting and Probability: the expectation, Markov-inequality, and union-bound arguments behind the Count–Min and Misra–Gries guarantees.
[^erickson-rand]: **Erickson**, Ch. — Randomized Algorithms: analysis of estimators by their expectation and variance, and the averaging trick that drives accuracy with independent copies.
[^btb-sketches]: Cormode & Muthukrishnan, "An improved data stream summary: the count-min sketch" (2005); Metwally, Agrawal & El Abbadi, "Efficient computation of frequent and top-k elements" (Space-Saving, 2005); Flajolet, Fusy, Gandouet & Meunier, "HyperLogLog" (2007); Heule, Nunkesser & Hall, "HyperLogLog in practice" (HyperLogLog++, 2013).