频繁项与 Heavy Hitters 问题

配对不变量 ​

每次全减可与“当前新项加 $k-1$ 个候选项”这 $k$ 个互异流位置配成一组并从分析中删除。全减次数至多 $m/k$，所以保存计数从不超过真实频率，且每个键的低估至多 $m/k$。

任何频率严格大于 $m/k$ 的键都不可能在这些互异组中被全部消去，因而一定留在候选表。这个证明依赖所有更新都是正的一次出现；给计数器直接处理负更新会失去“删除互异组”的证据。

${\ell }_1$、${\ell }_2$ 与 top-k ​

插入流中 $\varphi$-${\ell }_1$ heavy hitter 最多 $1/\varphi$ 个。General turnstile 的正负抵消要求明确取绝对频率和范数；CountSketch 用随机符号估计，并给出与去掉大坐标后的 ${\ell }_2$ 尾部相关的误差，适合这类模型。

频率 $(100,99,98)$ 的 top-2 必须区分 99 与 98；阈值 $0.2\Vert f{\Vert }_1$ 却可能把三者都报出。没有 frequency gap 时，固定名次对微小误差敏感，而 heavy-hitter 规格通过必报区、必不报区和灰区表达容忍度。

输出契约 ​

完整规格应列出必报区、必不报区、灰区、频率估计误差、失败概率、流模型和是否允许第二趟。只承诺候选表大小为 $O(1/\epsilon )$，不能推出无假阴性或计数准确。

在单位插入流和 ${\ell }_1$ 频率阈值下，Misra–Gries 摘要理路Misra–Gries 摘要Misra–Gries algorithm · Frequent algorithm以 k−1 个候选计数器确定性捕获频率超过流长 1/k 的所有元素。用至多 $k-1$ 个计数器捕获所有频率严格超过 $m/k$ 的键。为覆盖本页的闭阈值 $f_i\ge \varphi m$，取 $1/k<\varphi$；若还要满足宽度 $\eta$ 的灰区，取 $1/k\le \eta$，并报告满足 ${\hat{f}}_i\ge (\varphi -1/k)m$ 的候选。因为 $f_i-m/k\le {\hat{f}}_i\le f_i$，所有必报键都过筛，所有被报键又满足 $f_i\ge (\varphi -\eta )m$。空流直接返回空集。它不直接提供精确频率，也不覆盖带负更新的 turnstile 语义；需要精确输出时应再对候选做第二遍计数或接入独立验证层。

Heavy-hitter 规格把流量大户、热点键和高能坐标统一为带阈值与灰区的恢复问题。Misra–Gries 适合正更新下的 ${\ell }_1$ 候选，CountSketch 则面向 turnstile 与 ${\ell }_2$ 尾部；候选生成、频率验证和 top-$k$ 排名应按各自输出契约组合。