Heavy hitter
A frequency-threshold heavy hitter is a key whose count or nonnegative weight exceeds a specified share of the total over a defined observation window.
This record uses the strict convention f(x) > phi*N, where N is total observed mass and 0 < phi < 1. Other contracts use an inclusive threshold; record the convention. A top-k query instead selects the highest-frequency keys for a requested k, subject to available identities and a stated tie policy; it need not impose any minimum traffic share. [1] [2]
Candidate discovery, frequency estimation and exact verification are separate steps. Misra-Gries and Space-Saving retain key identities with bounds; bare Count-Min counters answer queries about supplied identities. Count-Min heavy-hitter constructions add candidate-tracking or hierarchical structures. An estimate is not an exact recount. [3] [2]
For a constructed three-request stream A B C, no key exceeds one third of the requests, although all tie for the highest count. Two-counter Misra-Gries returns no candidate at this strict boundary. The existing executable example records the complete input and result. [4]
Relations
Citations
- Jayadev Misra. A Proof of a Heavy Hitters Algorithm (2018), introduction and section 3.
- Metwally, Agrawal and El Abbadi. Efficient Computation of Frequent and Top-k Elements in Data Streams, sections 1 and 3-4.
- Cormode and Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and its Applications, sections 4.1 and 5.2.
- Hesela. Frequent-item certificates: strict-boundary example and executable checks.
Sources & caveats
- Scope is frequency or nonnegative-weight share (L1), not the separate L2 heavy-hitter definition based on squared frequencies.
- Request counts, byte weights and service-time weights answer different questions. Define key identity, counted unit, stream completeness and the window before interpreting a result.
- The weighted definition does not extend unit-insertion algorithm proofs to weighted updates, expiration, deletion or merging. Those need an explicit algorithm-specific contract.
- The worked example is constructed, not measured device traffic or a cache-performance benchmark.