Frequency Moments and the Tug-of-War Sketch

Let $f_1, \dots, f_m$ be the frequencies of the $m$ distinct items in a stream of length $n$. The $k$-th frequency moment is $F_k = \sum_i f_i^k$. Three of these moments are already familiar: $F_0$ is the number of distinct items, $F_1$ is the stream length (trivially known), and $F_2$ is the sum of squared frequencies, which measures how concentrated the stream is. A stream where one item appears $n$ times has $F_2 = n^2$; a stream of $n$ distinct items has $F_2 = n$. The ratio $F_2/F_1^2$ is a normalised concentration, and it decides how much space an exact frequency table would need.

$F_0$ is handled by HyperLogLog. $F_2$ needs a different idea, because it depends on multiplicities that a presence sketch discards. The Tug-of-War sketch computes it with a few hundred counters.

A random projection of the frequency vector

Pick a random vector $\sigma \in {-1, +1}^m$, one independent sign per item. The sketch maintains a single number

$$ X = \sum_{i=1}^{m} \sigma_i f_i $$

and updates it on each stream element by adding $\sigma_i$. That is the whole data structure: one integer, updated by a table lookup and an addition.

Now compute the expectation of $X^2$ over the random choice of $\sigma$:

$$ \mathbb{E}[X^2] = \sum_i \sigma_i^2 f_i^2 + \sum_{i \neq j} \sigma_i \sigma_j f_i f_j = \sum_i f_i^2 = F_2 $$

The cross terms vanish because $\sigma_i$ and $\sigma_j$ are independent and each has mean zero, so $\mathbb{E}[\sigma_i \sigma_j] = 0$. The diagonal terms are $\sigma_i^2 = 1$ with probability one. So a single counter, squared, is an unbiased estimator of $F_2$ — with enormous variance, since $X$ itself is a random variable of magnitude around $\sqrt{F_2}$ and its square fluctuates by a comparable relative amount.

The variance is the interesting part. For a stream with all mass on one item, $X = \pm n$ always and $X^2 = n^2$ exactly: zero variance. For a stream of $n$ distinct items each with frequency 1, $X$ is a sum of $n$ independent signs, so $X^2$ has mean $n$ and variance of order $n^2$. The estimator is worst exactly when the frequencies are uniform, which is also when $F_2$ is smallest and the absolute error is easiest to tolerate.

Averaging independent copies

The variance falls with independent repetitions. With $t$ independent sign vectors and counters $X_1, \dots, X_t$, the median-of-means estimator takes the average within groups and then the median across groups:

import statistics

class TugOfWar:
    """Median-of-means estimator for F2 over signed updates."""

    def __init__(self, groups, per_group, sign_of):
        # sign_of(item, j) returns +1 or -1, from a seeded hash
        self.g = groups
        self.k = per_group
        self.sign_of = sign_of
        self.acc = [[0] * per_group for _ in range(groups)]

    def add(self, item, delta=1):
        for gi in range(self.g):
            for j in range(self.k):
                self.acc[gi][j] += delta * self.sign_of(item, gi * self.k + j)

    def estimate_f2(self):
        # each group averages k independent squares, then median across groups
        means = [sum(v * v for v in row) / self.k for row in self.acc]
        return statistics.median(means)

Averaging $k$ independent copies reduces the variance by a factor of $k$, so the relative error falls as $1/\sqrt{k}$. Taking a median across $g$ groups converts a constant-probability large deviation into an exponentially small one: the median is bad only if more than half the group means are bad, which by a Chernoff bound costs a factor of $\log(1/\delta)$ in the group count.

The Alon–Matias–Szegedy analysis gives space $O(\log m \cdot \log(1/\delta) / \varepsilon^2)$ bits for a $1 \pm \varepsilon$ estimate with probability $1 - \delta$. The counter widths matter: each counter must hold a value up to $n$, so $O(\log n)$ bits each, and the sketch’s total size is the product of the counter count and the width. With 32-bit counters and 200 counters the sketch is 800 bytes, which is the usual order of magnitude for a practical implementation.

One practical simplification replaces the sign vectors with a four-wise independent family derived from a seed, rather than $m$-dimensional vectors stored explicitly. The variance argument only needs pairwise independence for the cross terms to vanish, and four-wise independence suffices for the variance of the variance, which is what the median-of-means analysis requires. A polynomial hash over a prime field evaluates such a family in constant time per element.

Turnstile updates and the L1 norm

Nothing in the construction requires positive updates. If an item’s frequency can decrease, the update adds $-\sigma_i$ instead of $+\sigma_i$, and the estimator is still unbiased for $F_2 = \sum_i f_i^2$. This is what makes the sketch usable for network traffic: a flow’s byte count can rise and fall as connections open and close, and the sketch tracks the sum of squared flow sizes without storing per-flow state.

The same counter array, with a different estimator, gives the $L_1$ difference between two streams. If the sketch is linear, then the sketch of the difference of two streams is the difference of their sketches. Feeding $X - X’$ into an estimator for $\sum_i |f_i - f_i’|$ requires a different construction — the geometric-median estimator of Feigenbaum et al. uses counters whose updates are drawn from a heavy-tailed distribution rather than signs — but the linearity that makes the difference computable is shared. This is the same principle that makes linear sketches for sparse recovery work: the sketch is a linear map, so differences of sketches are sketches of differences.

The $L_1$ norm itself, $\sum_i f_i$, is trivially the stream length and needs no sketch. The $L_1$ difference is not trivial, and it is the quantity that answers “how much did this traffic pattern change between two intervals”.

Higher moments and the limits of the method

The Tug-of-War construction extends to $F_k$ by using random variables with $k$-th moment 1 and mean zero, rather than signs. For even $k$, the estimator $\mathbb{E}[X^k]$ expands into a sum of products of the random variables; only terms where every index appears an even number of times survive the expectation, and the dominant surviving term is $\sum_i f_i^k$. The other surviving terms are smaller when $k$ is small, which is why the method gives good bounds for constant $k$ and degrades as $k$ grows.

For $k > 2$ the space requirement grows. Alon, Matias and Szegedy proved a matching lower bound: in the turnstile model, approximating $F_k$ for $k > 2$ needs $\Omega(m^{1-2/k})$ bits, which is polynomial in $m$ and, for small $k$, close to the cost of storing the frequencies outright. The transition is sharp: $F_2$ is cheap, $F_3$ and above are not, in a single pass with small space. The reason is that high moments are dominated by the largest frequency, and finding the largest frequency in a turnstile stream is itself hard when items can be decremented.

For $k < 2$ the picture reverses. $F_1$ is the stream length and needs no state at all, and $F_0$ costs $O(1/\varepsilon^2)$ registers. The moments with $0 < k < 2$ sit between those two cases and remain estimable in polylogarithmic space, using random variables drawn from a stable distribution rather than signs. The family of moments is therefore not uniformly difficult in $k$: the hard boundary is at $k = 2$, and it is crossed from above.

Bias, variance, and the median-of-means choice

The estimator $\mathbb{E}[X^2] = F_2$ is unbiased, but unbiasedness alone does not give a useful guarantee. The distribution of $X^2$ is heavy-tailed: for a stream with a single dominant item, $X^2$ is nearly constant, but for a mixed stream the tail of $X^2$ extends far above its mean, and the sample mean of a few copies is dominated by the largest copy. This is why the median of group means is used rather than the mean of all copies. The median tolerates a minority of badly high groups, while the mean does not.

The cost of that trade is a constant factor in the number of copies: the median-of-means estimator needs a constant multiple of the copies that a variance-optimal estimator would need, in exchange for exponential rather than polynomial failure probability. For a sketch with a few hundred counters the difference is irrelevant; for a sketch squeezed into a few dozen bytes it decides whether the error bound holds.

The deeper limitation is that all these guarantees are relative to $F_2$, not to $n$. An estimate of $F_2$ with 10 percent relative error is an estimate of the concentration of the stream with 10 percent relative error, and if the true $F_2$ is small — a uniform stream — then the absolute error is also small. But an application that wants to compare $F_2$ across streams of very different lengths must normalise first, because the sketch’s error is multiplicative in $F_2$ and not in $n$.

What the sketch cannot answer

Three queries are outside the construction’s reach.

Individual frequencies. The sketch compresses $m$ frequencies into a few hundred numbers, and by the counting argument it cannot recover any single $f_i$. For per-item estimates, Count-Min or Space-Saving is the right structure, and both trade a different error model — additive per-item error rather than global moment error — for the ability to answer point queries.

Exact values. Every estimate carries a relative error that the counter count sets: the median-of-means bound is $1 \pm \varepsilon$ for $\varepsilon$ around $1/\sqrt{t}$, so reaching 1 percent on $F_2$ needs on the order of ten thousand independent counters. The square-root law is unavoidable.

Ordering. The sketch is a sum, so it is invariant under permutation of the stream. Any question about the order of events — the longest run, the first occurrence, the size of a sliding window — is invisible to it. Those require structures that carry position, such as the timestamped buckets in sliding window aggregation.

The Tug-of-War sketch is best understood as a projection that preserves one scalar invariant of the frequency vector. It is cheap, mergeable by addition, indifferent to update sign, and precise to whatever degree the counter budget allows. Everything it cannot do follows from the fact that a projection discards the rest of the vector.