Misra-Gries summary
A Misra-Gries summary keeps a bounded set of labelled counters that contains every item exceeding a specified fraction of an insertion-only stream.
With m counters and N unit arrivals, increment a tracked key or allocate a free counter. If all counters are occupied by other keys, decrement each and discard the new arrival, removing zero counters. Every key with frequency strictly greater than N/(m+1) survives; equality is not enough. A surviving counter is a lower bound, not an exact count or a top-m ranking. [1] [2]
Let R be the remaining counter sum. The number of decrement rounds is D = (N-R)/(m+1). For any key, including an untracked key with counter zero, its true count lies between c and c+D. Candidates with c <= R/(m+1) cannot exceed the original strict threshold N/(m+1) and can be removed before an exact recount. [2] [1]
For the constructed stream A B C A B D A A A B with two counters, the result is A:3, B:1 and D=2. Exact counts are A:5, B:3, C:1, D:1. B can be rejected immediately: its upper bound 3 cannot exceed 10/3. The only remaining candidate is A. [3]
Relations
- related
- Space-Saving, Count-Min sketch, Cache admission
Citations
- Jayadev Misra. A Proof of a Heavy Hitters Algorithm, 7 February 2018, section 3.
- Agarwal, Cormode, Huang, Phillips, Wei and Yi. Mergeable Summaries, section 2, Lemmas 1-2.
- Hesela. Frequent-item certificates: exact examples, executable model and tests.
Sources & caveats
- The original algorithm is due to Misra and Gries (1982); the linked 2018 author note supplies the residual-candidate proof. Here m counts slots, so the note's k equals m+1.
- The example counts unit requests for exact identities, not bytes, latency or physical I/O. It is a deterministic illustration, not an empirical cache study.
- The stated guarantees cover cumulative unit insertions. Weighted updates, deletions, sliding windows and counter saturation require their own contracts.