Misra–Gries 摘要

更新规则 ​

处理insertion-only 流公理库插入流与 Turnstile 流Insertion-only stream · Turnstile stream以频率向量更新语义区分非负插入、严格 Turnstile 与一般正负流。 $a_1,\dots ,a_m$，维护至多 $k-1$ 个候选及计数：命中候选就加一；有空槽则以计数 1 加入；否则所有计数减一并删除零项。批量减一可理解为从当前元素与 $k-1$ 个不同候选中消去一组 $k$ 个互异出现。

误差证明 ​

设共执行 $D$ 次全体减一。每次消去 $k$ 个流元素，所以 $D\le m/k$。对任意元素 $x$，摘要计数 ${\hat{f}}_x$ 从不超过真实频率，且每轮消去至多损失 $x$ 的一次出现：

$$f_x-\frac{m}{k}\le {\hat{f}}_x\le f_x.$$

若 $f_x>m/k$ 而最终不在候选中，则 ${\hat{f}}_x=0$ 与下界矛盾，因此所有 heavy hitter 必在候选集。

可跟踪例子 ​

网络流依次出现 A、B、A、C，取 $k=3$。前三项后候选为 A:2、B:1；读 C 时无空槽，三种不同元素各消去一次，留下 A:1。B、C 被移除不代表真实频率为零，只表示它们尚未被证明超过 $m/3$。

输出与边界 ​

候选可能是假阳性，且计数是下界；若需精确报告超过阈值者，可对候选做第二遍真实计数。一般 turnstile 流含负更新，消去解释不再成立。参数是 $k-1$ 个计数器对应阈值 $m/k$；把计数器数直接写成 $k$ 会造成 off-by-one。朴素每轮全减 $O(k)$，需用摊还或共享偏移优化实现成本。

合并与加权更新 ​

两个分片摘要不能简单逐键相加后保留前 $k-1$ 名；可把候选及其摘要计数视作加权流，再运行同样的批量消去，把总误差预算相加。合并后仍需以全局流长解释 $m/k$。

正整数权重更新可一次增加计数并批量执行共同减量，而不逐个展开；证明要把每次消去的总权重计入 $D$。负权更新则没有“消去 $k$ 个不同出现”的证据，必须换 turnstile 算法。

计数误差从消去组得到 ​

设一共执行 $D$ 次“所有候选减一”。每次恰可配成 $k$ 个互异流元素，所以 $kD\le m$，即 $D\le m/k$。任意元素 $x$ 只有在未被计入候选或随一次全减时才损失一票，因此最终计数 ${\hat{f}}_x$ 满足

$$f_x-D\le {\hat{f}}_x\le f_x.$$

这给出确定性一侧误差；频率严格大于 $m/k$ 的元素不可能被完全消去，必在候选表中。

流 a,b,a,c,a,b、$k=3$ 时，前两项占满候选；读到第三种 c 会把 a,b,c 各消去一次，而后续 a,b 再建立计数。摘要最后可能低估实际次数，但不会制造不存在的重频元素。

候选身份和精确频率是两个问题。若要输出所有超过阈值的元素，可在可重读数据上第二遍精确计数；单遍且不能保存原流时，只能给候选与误差界，不能把摘要计数当真实频率。

参考资料

• Jayadev Misra, David Gries, Finding Repeated Elements, Science of Computer Programming, 1982.
• Erik Demaine, Alejandro López-Ortiz, J. Ian Munro, Frequency Estimation of Internet Packet Streams, ESA, 2002.