Heavy Hitters with Misra-Gries Counters and Space-Saving Buckets

The heavy hitter problem asks for every item whose frequency exceeds a threshold, conventionally $\phi N$ for stream length $N$ and threshold $\phi$. A hash table answers exactly and needs memory proportional to the number of distinct items. The two summaries here answer approximately with $k$ counters, and they are deterministic: no hash functions, no failure probability, no assumption about the input distribution. What they give up is precision on individual counts, and the way they give it up differs between the two.

The majority case, and why it generalises

Start with the simplest instance: find an item occurring more than half the time, if one exists. Two variables suffice. The first holds a candidate, the second a counter. An arriving item equal to the candidate increments the counter; a different item decrements it; when the counter reaches zero the candidate is replaced. At the end the candidate is the majority element if any exists.

The argument is an elimination argument. Every decrement pairs one occurrence of the candidate with one occurrence of a different item, and removes both from consideration. Each pair removes at most one occurrence of the true majority, so after all pairs are removed, more than zero occurrences of the majority remain — and the surviving candidate is it. The counter’s final value is a lower bound on the majority’s true count, specifically $f - (N - f)$, since at most $N - f$ non-majority items can have been paired against it.

Generalising to $k$ candidates replaces one counter with $k-1$ counters, all decremented together when a new item arrives and no counter is free. This is the Misra-Gries summary. Any item with $f > N/k$ survives, because eliminating it would require more than $N - N/k$ other items to pair against it, and there are fewer than that. The threshold and the counter budget are reciprocals: $k-1$ counters find items above $N/k$.

The invariant that makes the bound work

The Misra-Gries summary maintains a set of at most $k-1$ pairs (item, count) with this invariant: for every item $i$, the stored count $\hat{f}_i$ satisfies

$$ f_i - \frac{N - \hat{N}}{k} ;\leq; \hat{f}_i ;\leq; f_i $$

where $\hat{N} = \sum_j \hat{f}_j$ is the total of all stored counts. Each decrement round takes one unit out of every one of the $k-1$ counters and discards the item that triggered it, so the round accounts for $k$ units of stream mass that end up in no counter. The number of rounds is therefore $(N - \hat{N})/k$, and that is exactly the deficit bound.

The estimate is a lower bound on the true frequency, and the deficit is bounded by the number of rounds. An item not in the summary has $f_i \leq (N - \hat{N})/k \leq N/k$, which is the detection guarantee. An item in the summary has its count understated by at most the same amount.

from collections import defaultdict

class MisraGries:
    def __init__(self, k):
        self.k = k                 # at most k-1 counters
        self.counts = defaultdict(int)

    def add(self, item):
        if item in self.counts:
            self.counts[item] += 1
        elif len(self.counts) < self.k - 1:
            self.counts[item] = 1
        else:
            # no room: decrement every counter, drop those that reach zero
            for key in list(self.counts):
                self.counts[key] -= 1
                if self.counts[key] == 0:
                    del self.counts[key]

    def report(self):
        # stored counts are lower bounds; the caller applies its own threshold
        return dict(self.counts)

The loop over all counters on a failed insert is the algorithm’s cost centre: a single element can touch $k-1$ counters, so the worst-case per-element cost is $O(k)$. The amortised cost is $O(1)$ with no distributional assumption, because each round consumes $k$ units of stream mass and there are at most $N/k$ rounds, so the total decrement work over the stream is bounded by $N$. What varies with the data is the constant: for a skewed stream the decrement path is rare, while a stream that alternates among $k$ distinct items triggers a round on nearly every arrival. Implementations that care about tail latency bound $k$ accordingly.

Space-Saving inverts the error direction

Space-Saving keeps exactly $k$ counters, each holding an item and a count, and never decrements. An arriving item that matches a stored item increments its counter. An arriving item that matches nothing replaces the counter with the smallest count, setting that counter’s count to the minimum plus one and its item to the new arrival.

The replacement rule is the entire design. Because a counter is only ever incremented, and because an item’s counter can only be taken from it by a replacement that leaves the count one higher than the previous minimum, the stored count for a tracked item is an upper bound on its true frequency. The overestimate is bounded by the count of the counter that was displaced, and the smallest counter in the summary is at most $N/k$ — since $k$ counters hold $N$ total increments and the minimum is no larger than the average. So every stored estimate satisfies

$$ f_i ;\leq; \hat{f}_i ;\leq; f_i + \frac{N}{k} $$

and every item with $f_i > N/k$ is guaranteed to be present. The guarantee on which items are found is identical to Misra-Gries; the direction of the numeric error is opposite. Misra-Gries never overstates, Space-Saving never understates.

That difference matters for how the answers are used. A rate limiter that must not admit a client above its quota needs a count that is not understated, which points to Space-Saving. A billing system that must not overcharge needs a count that is not overstated, which points to Misra-Gries. Both need to know the sign of the error, and neither can get an unbiased estimate from these structures.

The replacement also needs the minimum efficiently. Scanning $k$ counters per arrival is $O(k)$; a min-heap over counters with lazy deletion gives $O(\log k)$, and the heap must be updated when a matched counter is incremented. An increment moves a counter up past only counters that already hold the new value, so that sift is short in practice, but the walk up the tree is still $O(\log k)$ in the worst case.

What the summaries cannot do, and why merging is expensive

Neither summary supports deletions in the sense Count-Min does with paired arrays. A negative update would have to decrement a counter, and a decrement can push a count below the truth, destroying the one-sided bound that the whole analysis rests on. Misra-Gries handles a decrement by treating it as a removal that may trigger a round of decrements, which is correct but requires knowing which counter holds the item and what its current count is — information the summary does have, so the operation is possible, but the error bound then applies to the net stream weight rather than the positive weight.

Merging two summaries is where the deterministic guarantees weaken. The natural merge sums counts for items present in both, keeps items present in only one, and then applies the pruning rule until at most $k-1$ counters remain. The error of the merged summary is bounded by the sum of the two input errors plus the error introduced by pruning. Over a tree of merges, the error accumulates with the depth of the tree: a stream partitioned into $p$ parts merged in a balanced tree of depth $\log p$ carries an error term proportional to $(N/k)\log p$ rather than $N/k$. This is the general phenomenon for mergeable summaries — the guarantee holds, but the constant grows with the merge topology — and it is why distributed deployments either merge shallowly or allocate more counters per node than the global threshold requires.

Space-Saving is not mergeable in the same clean way. Its counters are upper bounds tied to a specific displacement history; merging two sets of upper bounds by taking maxima is not sound, and merging by summing is also not sound because a key may appear in both summaries with different displacement baselines. The practical approach for distributed counting is to use a mergeable structure — Count-Min with identical hashes, as described in Count-Min error bounds — or to accept a two-stage design where each node reports its local heavy hitters and the coordinator merges candidate lists.

Thresholds, guarantees, and the gap between them

Every statement above is about items above the threshold. Nothing is promised about items below it.

Misra-Gries will report items with frequency as low as just above zero, since any item that entered a counter and was never eliminated stays. The report is therefore a superset of the true heavy hitters, with a false-positive region between zero and $N/k$. Space-Saving reports exactly $k$ items, some of which may be far below the threshold, and the reported counts let the caller filter by the estimate — but an item with a true count just under $N/k$ may be reported with an estimate above it.

The threshold is also not a free parameter in the way it appears. Choosing $\phi$ small enough that $1/\phi$ counters fit in memory is the standard sizing rule, but the guarantee is only for items above $\phi N$, and the stream length $N$ is often unknown when the summary is initialised. A summary sized for a billion events and applied to a stream of a million will find nothing useful, because the threshold is set by the counters rather than the stream. Adaptive schemes grow $k$ as the stream lengthens, at the cost of rebuilding the summary on each growth.

The other classical answer to the same problem is lossy counting, which divides the stream into windows of width $\lceil 1/\varepsilon \rceil$ and decrements every counter by one at each window boundary, dropping zeros. It guarantees that every item with $f > \varepsilon N$ has an entry at the end of the stream, and that every surviving entry’s count is at most $\varepsilon N$ below its item’s true frequency. It is a different point on the same trade: the guarantee is two-sided in exchange for the counter budget depending on $\varepsilon$ rather than on the threshold.

Choosing between the two

The decision reduces to four questions, and the answers are usually determined by the application rather than by the algorithms.

• Which direction of error is tolerable? Overestimation for admission control, underestimation for accounting.
• Is the stream skewed? Both structures perform best when a few items dominate; for a near-uniform stream every item sits near $N/k$ and the summaries are uninformative.
• Must summaries merge across nodes? If so, prefer a linear sketch, or budget for error growth with merge depth.
• How is the threshold set? Fixed $k$ means the effective threshold depends on stream length, which must be estimated in advance or tracked adaptively.

The counters here compress the frequency vector while preserving its head. That is a different kind of compression from the projections in the Tug-of-War sketch, which keep a global statistic and lose the identities, and different again from the register maxima in HyperLogLog, which keep presence and lose multiplicity. Which one is appropriate follows from which question is being asked; together they cover identity, aggregate concentration, and presence.