heavy-hitter · research · also Frequent item, Frequency-threshold heavy hitter

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.

Related Observatory article: Read on hesela.com

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

related
Misra-Gries summary, Space-Saving, Count-Min sketch, Cache admission

Citations

  1. Jayadev Misra. A Proof of a Heavy Hitters Algorithm (2018), introduction and section 3. (accessed 2026-11-20)
  2. Metwally, Agrawal and El Abbadi. Efficient Computation of Frequent and Top-k Elements in Data Streams, sections 1 and 3-4. (accessed 2026-11-20)
  3. Cormode and Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and its Applications, sections 4.1 and 5.2. (accessed 2026-11-20)
  4. Hesela. Frequent-item certificates: strict-boundary example and executable checks. (accessed 2026-11-20)
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.

JSON: /data/terms/heavy-hitter.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Heavy hitter. Hesela. 2026-11-20. https://hesela.dev/terms/heavy-hitter/