misra-gries · research · also Misra-Gries algorithm, Frequent algorithm

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

  1. Jayadev Misra. A Proof of a Heavy Hitters Algorithm, 7 February 2018, section 3. (accessed 2026-11-20)
  2. Agarwal, Cormode, Huang, Phillips, Wei and Yi. Mergeable Summaries, section 2, Lemmas 1-2. (accessed 2026-11-20)
  3. Hesela. Frequent-item certificates: exact examples, executable model and tests. (accessed 2026-11-20)
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.

JSON: /data/terms/misra-gries.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Misra-Gries summary. Hesela. 2026-11-20. https://hesela.dev/terms/misra-gries/