定义族
对频率向量 (f)，坐标 (i) 是 ((\phi,p)) heavy hitter，若
取 (p=1) 或 (p=2) 分别得到 (\ell_1) 与 (\ell_2) 版本。在insertion-only 或 strict turnstile 流中频率非负，绝对值可以省略；general turnstile 允许正负抵消，必须保留它。近似输出还要定义必报区、必不报区与灰区。
流量大户是实例。Top-(k) 必须返回固定数量，即使第 (k) 与 (k+1) 名几乎相同；heavy hitters 按阈值，可能返回零项或多项，二者不等价。
Misra–Gries 状态
给定参数 (k)，Misra–Gries 维护至多 (k-1) 个键计数器。新项命中候选则加一；有空槽则以计数 1 插入；否则所有计数器减一，并删除变为 0 的项。
取 (k=3)，流为 (a,b,a,c,a,b)。状态依次是 ({a:1})、({a:1,b:1})、({a:2,b:1})；读到 (c) 时全减并删除 (b)，得到 ({a:1})；最后两项使状态成为 ({a:2,b:1})。
真实频率为 (f_a=3,f_b=2,f_c=1)。候选计数不是精确频率：a 被低估 1，b 被低估 1。若接口需要输出真实超过阈值的项，可在允许二次扫描时只对候选重新计数。
配对不变量
每次全减可与“当前新项加 (k-1) 个候选项”这 (k) 个互异流位置配成一组并从分析中删除。全减次数至多 (m/k)，所以保存计数从不超过真实频率，且每个键的低估至多 (m/k)。
任何频率严格大于 (m/k) 的键都不可能在这些互异组中被全部消去，因而一定留在候选表。这个证明依赖所有更新都是正的一次出现；给计数器直接处理负更新会失去“删除互异组”的证据。
(\ell_1)、(\ell_2) 与 top-k
插入流中 (\phi)-(\ell_1) heavy hitter 最多 (1/\phi) 个。General turnstile 的正负抵消要求明确取绝对频率和范数；CountSketch 用随机符号估计，并给出与去掉大坐标后的 (\ell_2) 尾部相关的误差，适合这类模型。
频率 ((100,99,98)) 的 top-2 必须区分 99 与 98；阈值 (0.2\lVert f\rVert_1) 却可能把三者都报出。没有 frequency gap 时，固定名次对微小误差敏感，而 heavy-hitter 规格通过必报区、必不报区和灰区表达容忍度。
输出契约
完整规格应列出必报区、必不报区、灰区、频率估计误差、失败概率、流模型和是否允许第二趟。只承诺候选表大小为 (O(1/\varepsilon))，不能推出无假阴性或计数准确。
参考资料
- Misra, Gries, “Finding Repeated Elements,” 1982.
- Cormode, Hadjieleftheriou, “Finding Frequent Items in Data Streams,” VLDB 2008.