Misra-Gries & Space-Saving Invariants

Counters That Refuse to Forget the Heavy Keys

Imagine a small noticeboard at a busy help desk. It has room for only three issue labels, but thousands of requests arrive. A label that keeps reappearing should survive, while one-off issues should cancel one another or be replaced. Misra–Gries and Space-Saving turn this intuition into deterministic streaming algorithms: no random hash event is needed for their core guarantees.

Both algorithms maintain a bounded table of key–counter pairs for an insertion-only stream. When an observed key is already present, its counter rises. Their behavior diverges when an untracked key arrives and the table is full. Misra–Gries (MG) decrements every stored counter and discards zeros; this is counter cancellation. Space-Saving (SS) replaces a minimum-count entry with the new key, assigns the new estimate one more than that minimum, and records the old minimum as an error certificate.

For a tiny MG trace with two counters and stream \(A,B,C,A,A\): after \(A,B\), both counters equal one. The unseen \(C\) meets a full table, so the conceptual group \(A,B,C\) is cancelled and the table empties. The final two \(A\)'s leave \(A:2\). Its exact frequency is three, and the missing one is explained by the single cancellation round. With two SS counters, the arrival of \(C\) instead replaces one minimum entry of estimate one; the new \(C\) entry receives estimate two and error one. It admits that up to one earlier occurrence may be falsely attributed to \(C\).

This deep dive builds on heavy hitters by proving why a bounded candidate table cannot lose a sufficiently frequent key. A residual stream is what remains after deleting conceptual groups of distinct items represented by MG cancellations. A candidate bound states how many keys can be retained and which true heavy keys must be among them. MG counters are lower estimates; SS counters are upper estimates for tracked keys. Neither table alone proves that every retained candidate is truly heavy—an exact second pass or separate verification sketch may still be required.

The stream model matters. The standard invariants here assume unit, positive arrivals. Arbitrary deletions break the cancellation and replacement proofs. Weighted positive updates require a carefully specified weighted variant, not a loop-free reuse of the unit-update pseudocode. Counter overflow, inconsistent key identity, and incorrect tie handling can also invalidate an otherwise deterministic theorem.

The Misra-Gries Cancellation Invariant

Fix the convention: MG stores at most \(k\) key–counter pairs and processes unit positive arrivals. For item \(x\):

1. If \(x\) is tracked, increment its counter.
2. Else, if fewer than \(k\) keys are tracked, insert \(x\) with count one.
3. Else decrement every stored counter by one and remove zeros; do not insert \(x\) during that update.

Every execution of step 3 can be interpreted as deleting \(k+1\) distinct stream occurrences: the new untracked \(x\), plus one occurrence attributed to each of the \(k\) tracked keys. Let \(D\) be the number of such cancellation rounds. These groups are disjoint, so \[ (k+1)D\le n,\qquad D\le\left\lfloor\frac{n}{k+1}\right\rfloor. \]

After deleting all conceptual groups, the residual multiplicity of every retained item equals its stored counter. For any item \(i\), tracked or not, define \(c_i=0\) when absent. Each cancellation can remove at most one occurrence of \(i\), hence \[ 0\le f_i-c_i\le D\le\left\lfloor\frac{n}{k+1}\right\rfloor. \] This is the central invariant. It immediately proves the candidate theorem: if \(f_i>n/(k+1)\), then \(c_i>0\), so \(i\) must be in the final table. It also gives a deterministic frequency interval \(c_i\le f_i\le c_i+D\). A second pass over only the candidates removes false positives.

The strict inequality matters. At exactly \(n/(k+1)\), an item may vanish. For \(k=2\), stream \(A,B,C\) has every frequency equal to one and \(n/(k+1)=1\); the single cancellation empties the table. Another convention uses \(k-1\) counters and states the threshold as \(n/k\). Both are correct, but mixing the symbol conventions creates an off-by-one theorem.

The proof is order-independent in its guarantee even though the final candidate set and counters can depend on order. It is deterministic: no independence or probability assumption exists. But it is not a general-turnstile proof; a negative update cannot be placed into a \(k+1\)-distinct positive cancellation group. Compared with exact counting, MG trades exact identities below the threshold for \(O(k)\) memory.

flowchart TD
    A[Insertion-only unit stream] --> B[At most k tracked keys]
    B --> C{Incoming key tracked or free slot?}
    C -->|yes| D[Increment or insert]
    C -->|no| E[Full-table cancellation]
    E --> F[Delete k tracked occurrences plus incoming one]
    F --> G[Each round accounts for k plus 1 items]
    G --> H[D at most floor of n over k plus 1]
    H --> I[For every key zero to D occurrences cancelled]
    I --> J[Stored count is lower bound]
    J --> K[Frequency above n over k plus 1 must survive]
    A --> L{Negative or malformed update?}
    L -->|yes| M[Cancellation interpretation fails]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,F,G,H purple;
    class I,J,K teal;
    class L,M crimson;

Space-Saving Replacement and Error Certificates

Space-Saving also keeps \(k\) entries, each containing key, estimate \(\widehat f\), and error \(\varepsilon\). A tracked arrival increments its estimate. A free slot gets estimate one and error zero. When the table is full and an unseen \(x\) arrives, find an entry of minimum estimate \(m\), replace its key by \(x\), and store \((\widehat f_x,\varepsilon_x)=(m+1,m)\).

The inherited \(m\) is not claimed as observed frequency of \(x\); it is uncertainty. For every tracked key, \[ \widehat f_i-\varepsilon_i\le f_i\le\widehat f_i. \] The lower endpoint counts occurrences definitely seen since insertion; the upper endpoint allows for occurrences before tracking. For an untracked key, its frequency is at most the current minimum estimate. The sum of table estimates equals the processed stream length once the table is full (and also before full if all mass is represented), so the minimum is at most \(n/k\). Consequently the maximum overestimate is bounded by roughly \(n/k\), and any item with frequency greater than \(n/k\) must be tracked.

Example with \(k=2\): process \(A,A,B,C\). After \(A,A,B\), entries are \(A:(2,0)\) and \(B:(1,0)\). On \(C\), replace \(B\), producing \(C:(2,1)\). The certificate says \(1\le f_C\le2\); exact \(f_C=1\). A later \(C\) yields \(C:(3,1)\), hence \(2\le f_C\le3\), exact \(2\). The estimate stays an upper bound while the certified interval narrows proportionally for a growing key.

Tie-breaking among equal minima can change which light key is stored, but not the invariant if a true minimum is selected. A stale heap entry, overflow, or replacing a nonminimum entry can break the global error bound. SS is often empirically stronger at ranking heavy items than MG because it immediately admits new contenders, though MG's cancellation proof is especially transparent and its counters are lower bounds.

from collections import Counter

class MisraGries:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.k = capacity
        self.counts = {}
        self.cancellations = 0

    def update(self, key):
        if key in self.counts:
            self.counts[key] += 1
        elif len(self.counts) < self.k:
            self.counts[key] = 1
        else:
            self.cancellations += 1
            for candidate in list(self.counts):
                self.counts[candidate] -= 1
                if self.counts[candidate] == 0:
                    del self.counts[candidate]

class SpaceSaving:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.k = capacity
        self.entries = {}  # key -> [estimate, error]

    def update(self, key):
        if key in self.entries:
            self.entries[key][0] += 1
        elif len(self.entries) < self.k:
            self.entries[key] = [1, 0]
        else:
            victim = min(self.entries, key=lambda x: (self.entries[x][0], str(x)))
            minimum = self.entries.pop(victim)[0]
            self.entries[key] = [minimum + 1, minimum]

def verify(stream, capacity):
    exact = Counter(stream)
    mg, ss = MisraGries(capacity), SpaceSaving(capacity)
    for key in stream:
        mg.update(key)
        ss.update(key)

    n = len(stream)
    assert mg.cancellations <= n // (capacity + 1)
    for key, truth in exact.items():
        stored = mg.counts.get(key, 0)
        assert 0 <= truth - stored <= mg.cancellations
        if truth > n / (capacity + 1):
            assert key in mg.counts

    for key, (estimate, error) in ss.entries.items():
        assert estimate - error <= exact[key] <= estimate
    for key, truth in exact.items():
        if truth > n / capacity:
            assert key in ss.entries
    return exact, mg, ss

stream = list("aaaaaaaaaabbbbbccdefghijk")
exact, mg, ss = verify(stream, 3)

verify([], 2)
verify(list("abcabcabcabc"), 1)
verify(list("abcdefgh") + ["hot"] * 9 + list("ijklmnop"), 3)

try:
    MisraGries(0)
    raise AssertionError("zero capacity accepted")
except ValueError:
    pass

print("exact heavy keys:", exact.most_common(3))
print("MG:", mg.counts, "cancellations:", mg.cancellations)
print("SS:", ss.entries)

Tracking Hot Keys with Bounded Tables

In a teaching setting, MG with two counters and colored tokens makes the invariant physical: whenever a third distinct token arrives to a full table, remove one token of every represented color plus the newcomer. Counting removed groups proves the error bound.

In production, imagine an API gateway processing \(5\times10^7\) successful request events per minute and reporting hot route–tenant pairs. Space-Saving can maintain a small online ranking with per-entry uncertainty. A verification tier then exact-counts the reported candidates for alerting. The capacity follows the smallest frequency fraction worth detecting: \(k\) should exceed the reciprocal threshold, with operational headroom for near-threshold keys.

MG may be preferable in a pipeline where the proof and a conservative lower count matter more than ranking quality. Neither standard algorithm should be selected when events include retractions or negative weights. For distributed aggregation, arbitrary table merging is not simply table addition; use a proven mergeable summary procedure or centralize updates. Evidence that invalidates deployment includes certificate violations against sampled exact counts, candidate misses above the theorem threshold, counter overflow, non-unit events entering the path, or error dominated by key-canonicalization mistakes.

An adversary can exploit a small table by sending many distinct light keys around a target. The theorem still holds for a target above its strict threshold, but near-threshold candidates may churn and reported rankings may become operationally noisy. Rate limits, identity normalization, exact verification, and monitoring distinct-key velocity are trust-boundary controls.

flowchart TD
    A[Define heavy threshold and decision cost] --> B{Unit positive stream?}
    B -->|no| C[Reject standard MG and SS]
    B -->|yes| D{Need transparent lower counts?}
    D -->|yes| E[Evaluate Misra-Gries]
    D -->|no| F{Need strong online ranking?}
    F -->|yes| G[Evaluate Space-Saving]
    F -->|no| H[Compare exact or sketch alternatives]
    E --> I[Choose capacity from threshold]
    G --> I
    I --> J[Validate against exact sampled windows]
    J --> K{Candidate and certificate checks pass?}
    K -->|no| L[Reject resize or repair pipeline]
    K -->|yes| M[Deploy with exact candidate verification]
    M --> N[Monitor churn overflow and stream model]
    N --> O{Assumptions still hold?}
    O -->|yes| N
    O -->|no| L
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,D,F,H navy;
    class E,G,I purple;
    class J,M,N teal;
    class C,K,L,O crimson;

Trace and Extend Frequent-Item Counters

Mastery begins with stating the counter convention before quoting a threshold. Reconstruct MG from its \(k+1\)-item cancellation groups, derive \(D\le n/(k+1)\), and turn that into both an interval and a candidate theorem. Then reconstruct SS replacement, explain why the old minimum becomes error, and prove the stored interval by induction.

Practice should include exact traces, not only code. Record the entire table after each arrival, MG cancellation count, and every SS error field. Compare with an exact frequency map. Debug variants that insert the incoming MG key after decrement, forget to delete zero counters, reset SS error to zero, replace a nonminimum entry, or use a too-small numeric type. Each defect should be tied to a failed proof step.

For extension, study weighted positive updates, mergeable frequent-item summaries, and verification with Count-Min or exact second passes. Do not assume a unit algorithm automatically supports these variants. The next conceptual bridge is from deterministic candidate retention to probabilistic point-query sketches and distributed summary composition.