Streaming Sketches

This builds on 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.

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.

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

Algorithm 3:Count–Min sketch —

\textsc{Update}

and

\textsc{Query}

1
procedure $\textsc{Update}(a)$
record one occurrence of item $a$
2
for $r \gets 1$ to $d$ do
3
$C[r][\,h_r(a)\,] \gets C[r][\,h_r(a)\,] + 1$
bump one cell per row
4
procedure $\textsc{Query}(a)$
estimate the frequency of $a$
5
$\hat f \gets +\infty$
6
for $r \gets 1$ to $d$ do
7
$\hat f \gets \min\parens{\hat f,\; C[r][\,h_r(a)\,]}$
tightest row wins
8
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, 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$ .

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

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)] \geq f_{a}$ always, and the minimum is the row with the least colliding mass.

Choosing the grid. The parameters translate directly into memory. For a $0.1%$ additive error ( $ε = 0.001$ ) with $99%$ confidence ( $δ = 0.01$ ): $w = ⌈ e /0.001 ⌉ = 2719$ columns and $d = ⌈ ln 100 ⌉ = 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 $ε ∥ f ∥_{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 $ε ∥ f ∥_{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.

count_min_sketch.pypython

from __future__ import annotations

import math
import random
from collections.abc import Hashable
from typing import Generic, Optional, TypeVar

ItemType = TypeVar("ItemType", bound=Hashable)

class CountMinSketch(Generic[ItemType]):
  """
    An approximate frequency table over hashable items.\n
    `width` columns and `depth` rows fix the space; `update` records\n
    occurrences and `query` returns a never-underestimating count.\n
  """

  def __init__(
    self,
    width: int = 272,
    depth: int = 5,
    seed: Optional[int] = None,
  ) -> None:
    if width < 1 or depth < 1:
      raise ValueError("width and depth must be at least 1")

    # a depth-by-width grid of counters, all starting at zero.
    self.width: int = width
    self.depth: int = depth
    self.total: int = 0
    self._counts: list[list[int]] = [[0 for _ in range(width)] for _ in range(depth)]

    # one random salt per row gives the rows independent hash functions.
    salt_source: random.Random = random.Random(seed)
    self._salts: list[int] = [
      salt_source.randrange(2**61) for _ in range(depth)
    ]

  @classmethod
  def from_error(
    cls,
    epsilon: float,
    delta: float,
    seed: Optional[int] = None,
  ) -> CountMinSketch[ItemType]:
    """
      Build a sketch sized for additive error epsilon * total with\n
      failure probability at most delta: width = ceil(e / epsilon),\n
      depth = ceil(ln(1 / delta)).\n
    """
    if not (0.0 < epsilon < 1.0) or not (0.0 < delta < 1.0):
      raise ValueError("epsilon and delta must lie in (0, 1)")

    # width tightens the error bound; depth drives down the failure odds.
    width: int = math.ceil(math.e / epsilon)
    depth: int = math.ceil(math.log(1.0 / delta))
    return cls(width=width, depth=depth, seed=seed)

  def _columns(self, item: ItemType) -> list[int]:
    """
      The chosen column in each row for `item`.\n
    """
    base: int = hash(item)
    return [
      (base ^ salt) % self.width for salt in self._salts
    ]

  def update(self, item: ItemType, count: int = 1) -> None:
    """
      Add `count` occurrences of `item`, bumping one cell per row.\n
    """
    if count < 0:
      raise ValueError("count must be non-negative")

    # bump the chosen cell in every row and track the grand total.
    self.total += count
    for row, column in enumerate(self._columns(item)):
      self._counts[row][column] += count

  def query(self, item: ItemType) -> int:
    """
      The estimated frequency of `item`: the minimum across the rows.\n
      Always at least the true count.\n
    """
    return min(
      self._counts[row][column]
      for row, column in enumerate(self._columns(item))
    )

Misra–Gries: heavy hitters in $O (1/ ε)$ counters

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

Idea. Keep at most $k - 1$ labelled counters, where $k = ⌈ 1/ ε ⌉$ . 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 4:

\textsc{MisraGries}(\text{stream}, k)

— heavy-hitter candidates in

k - 1

counters

1
$T \gets$ empty map
at most $k - 1$ labelled counters
2
for each item $x$ do
3
if $x \in T$ then
4
$T[x] \gets T[x] + 1$
$x$ already holds a counter
5
else if $|T| < k - 1$ then
6
$T[x] \gets 1$
a counter is free: claim it
7
else
table full, $x$ unmatched: decrement round
8
for each label $y$ in $T$ do
9
$T[y] \gets T[y] - 1$
10
if $T[y] = 0$ then remove $y$ from $T$
evict at zero
11
return $T$
candidates with estimates $\hat f_y = T[y]$

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.

A worked trace. Run Misra–Gries with $k - 1 = 2$ counters ( $k = 3$ , so $ε = 1/3$ ) on the seven-item stream $a b a c a b a$ , where $f_{a} = 4$ , $f_{b} = 2$ , $f_{c} = 1$ .

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

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

⌊ n / k ⌋ = ⌊ 7/3 ⌋ = 2

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

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/ ε)$ 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.

misra_gries.pypython

from __future__ import annotations

import math
from collections.abc import Hashable
from typing import Generic, TypeVar

ItemType = TypeVar("ItemType", bound=Hashable)

class MisraGries(Generic[ItemType]):
  """
    A streaming heavy-hitter summary with at most `slots` counters.\n
    `offer` feeds one item; `counts` exposes the surviving estimates;\n
    `heavy_hitters` returns the candidates above a frequency threshold.\n
  """

  def __init__(self, slots: int) -> None:
    if slots < 1:
      raise ValueError("slots must be at least 1")

    # `slots` labelled counters, total items seen, and the live counter table.
    self.slots: int = slots
    self.length: int = 0
    self._counters: dict[ItemType, int] = {}

  @classmethod
  def from_epsilon(cls, epsilon: float) -> MisraGries[ItemType]:
    """
      Build a summary with k-1 counters for k = ceil(1 / epsilon), so the\n
      stored count of any item is at least its true count minus epsilon * n.\n
    """
    if not (0.0 < epsilon < 1.0):
      raise ValueError("epsilon must lie in (0, 1)")

    # k = ceil(1 / epsilon) counters, minus one, never below a single slot.
    bound: int = math.ceil(1.0 / epsilon)
    return cls(slots=max(1, bound - 1))

  def offer(self, item: ItemType) -> None:
    """
      Process one stream item by the three-way Misra–Gries rule.\n
    """
    self.length += 1

    # a held label increments; a free slot is claimed; otherwise decrement all.
    if item in self._counters:
      self._counters[item] += 1
    elif len(self._counters) < self.slots:
      self._counters[item] = 1
    else:
      # this round cancels `slots` + 1 distinct arrivals at once.
      for label in self._counters:
        self._counters[label] -= 1

      # drop every counter the decrement just emptied.
      emptied = [label for label, c in self._counters.items() if c == 0]
      for label in emptied:
        del self._counters[label]

  def counts(self) -> dict[ItemType, int]:
    """
      A copy of the surviving (label, count) estimates.\n
    """
    return dict(self._counters)

  def estimate(self, item: ItemType) -> int:
    """
      The stored count of `item`, or 0 if it holds no counter.\n
    """
    return self._counters.get(item, 0)

  def heavy_hitters(self, threshold: float) -> list[ItemType]:
    """
      Every surviving label whose stored count exceeds threshold * n.\n
      A superset of the true heavy hitters (no false negatives), so a\n
      verifying second pass can prune the rest.\n
    """
    cutoff: float = threshold * self.length
    return [
      label
      for label, count in self._counters.items()
      if count > cutoff
    ]

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 $Ω (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, $ρ$ . A leading run of $ρ$ zeros occurs with probability $2^{- ρ}$ , 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.

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.

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 $ρ (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 ρ$ 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 5:

\textsc{HyperLogLog}(\text{stream}, m = 2^{b})

— distinct-count estimation

1
$M[1 \dots m] \gets 0$
one register per bucket
2
for each item $x$ do
3
$u \gets h(x)$
uniform bit string
4
$j \gets 1 + \text{int}(u_1 u_2 \dots u_b)$
first $b$ bits pick a bucket
5
$\rho \gets$ position of first $1$ bit in $u_{b+1} u_{b+2} \dots$
6
$M[j] \gets \max\parens{M[j],\; \rho}$
registers only ever grow
7
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

\overset{n}{^} = α_{m} m \cdot harmonic mean of 2^{M [j]} \frac{m}{\sum _{j = 1}^{m} 2 ^{- M [j]}},

where $α_{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/ 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

j \sum 2^{- M [j]} = \frac{1}{4} + \frac{1}{8} + \frac{1}{2} + \frac{1}{4} = \frac{9}{8}, \overset{n}{^} = α_{4} \cdot \frac{4 ^{2}}{9/8} = α_{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 $\overset{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.

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.

hyperloglog.pypython

from __future__ import annotations

import hashlib
import math
from collections.abc import Hashable
from typing import Generic, TypeVar

ItemType = TypeVar("ItemType", bound=Hashable)

_HASH_BITS: int = 64

def _stable_hash(item: Hashable) -> int:
  """
    A stable 64-bit hash, independent of the process-wide hash seed, so\n
    estimates are reproducible across runs.\n
  """
  digest: bytes = hashlib.blake2b(repr(item).encode("utf-8"), digest_size=8)\
    .digest()
  return int.from_bytes(digest, "big")

def _leading_zeros_plus_one(value: int, width: int) -> int:
  """
    One more than the number of leading zeros in the low `width` bits of\n
    `value` — the position of the first set bit, counted from the top.\n
  """
  # scan from the most significant bit of the window down to the first set bit.
  for offset in range(width):
    if value & (1 << (width - 1 - offset)):
      return offset + 1

  # all-zero window: one past the width.
  return width + 1

class HyperLogLog(Generic[ItemType]):
  """
    A probabilistic cardinality estimator over hashable items.\n
    `precision` bits choose among m = 2^precision buckets; `add` records an\n
    item and `count` reads back the estimated number of distinct items.\n
  """

  def __init__(self, precision: int = 14) -> None:
    if not (4 <= precision <= 16):
      raise ValueError("precision must lie in [4, 16]")
    self.precision: int = precision
    self.bucket_count: int = 1 << precision
    self._registers: list[int] = [0 for _ in range(self.bucket_count)]

    # bias-correction constant alpha_m: small bucket counts are tabulated,
    # larger ones use the asymptotic formula (both from the HLL paper).
    tabulated: dict[int, float] = {16: 0.673, 32: 0.697, 64: 0.709}
    asymptotic: float = 0.7213 / (1.0 + 1.079 / self.bucket_count)
    self._alpha: float = tabulated.get(self.bucket_count, asymptotic)

  def add(self, item: ItemType) -> None:
    """
      Fold one item into the sketch, updating its bucket's register to the\n
      largest leading-zero run seen there.\n
    """
    fingerprint: int = _stable_hash(item)

    # top `precision` bits select the bucket; the rest feed the run length.
    bucket: int = fingerprint >> (_HASH_BITS - self.precision)
    tail_width: int = _HASH_BITS - self.precision
    tail: int = fingerprint & ((1 << tail_width) - 1)

    # keep the longest leading-zero run ever seen for this bucket.
    run: int = _leading_zeros_plus_one(tail, tail_width)
    self._registers[bucket] = max(self._registers[bucket], run)

  def count(self) -> int:
    """
      The estimated number of distinct items added so far, with the small-\n
      and large-range corrections from the original HyperLogLog analysis.\n
    """
    raw: float = self._raw_estimate()

    # small-range correction via linear counting over empty buckets.
    if raw <= 2.5 * self.bucket_count:
      empty: int = self._registers.count(0)
      if empty > 0:
        return round(
          self.bucket_count * math.log(self.bucket_count / empty)
        )

    return round(raw)

  def _raw_estimate(self) -> float:
    """
      The harmonic-mean estimate before range corrections.\n
    """
    harmonic: float = sum(
      2.0 ** (-register) for register in self._registers
    )
    return self._alpha * self.bucket_count**2 / harmonic

  def merge(self, other: HyperLogLog[ItemType]) -> None:
    """
      Fold another sketch (same precision) into this one by taking the\n
      element-wise maximum of the registers — the union's cardinality.\n
    """
    if other.precision != self.precision:
      raise ValueError("cannot merge sketches of differing precision")

    # element-wise max of the registers is the union sketch.
    self._registers = [
      max(mine, theirs)
      for mine, theirs in zip(self._registers, other._registers)
    ]

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/ ε)$ 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.²

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 (ε^{- 1} log (1/ δ))$ counters	$f_{a} \leq \hat{f}_{a} \leq f_{a} + ε n$ w.p. $1 - δ$
which items are frequent?	Misra–Gries	$O (1/ ε)$ counters	$f_{a} - ε n \leq \hat{f}_{a} \leq f_{a}$ , deterministic
how many distinct items?	HyperLogLog	$O (m log log n)$ bits	relative error $\approx 1.04/ 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} \geq f_{a}$ ) and additive, $\hat{f}_{a} \leq f_{a} + ε ∥ f ∥_{1}$ with probability $1 - δ$ , 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/ ε)$ counters with the deterministic sandwich $f_{a} - ε n \leq \hat{f}_{a} \leq 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/ 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, App. C — Counting and Probability: the expectation, Markov-inequality, and union-bound arguments behind the Count–Min and Misra–Gries guarantees. ↩
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). ↩