CountSketch

符号哈希先把碰撞键随机翻转，使它们的贡献围绕零而不是单向累加；桶哈希再把总尾部能量分摊到多个桶。不同重复行给出彼此独立的噪声样本，中位数忽略少数灾难性碰撞，所以最终保证自然以 $L_2$ 尾部能量而非全局 $L_1$ 质量计量。

正负碰撞例子 ​

turnstile 流中两个其他键可能与目标同桶。一个符号与目标同号、另一个反号时，噪声相互抵消；不同重复行重新抽桶和符号，单行偶然大偏差不会主导中位数。这也是它比 Count–Min 更适合有正负更新与 $L_2$ heavy hitters 的原因。

边界与对照 ​

估计可高可低，不提供单调上界。把行间中位数换成平均会让少数重尾碰撞破坏同样的失败概率；桶哈希和符号哈希需要规定独立性。Count–Min公理库Count–Min SketchCount-Min Sketch · CMS用多行哈希计数器给非负频率提供不低估、带全局 L1 加性误差的点查询。给非负流的一侧 $L_1$ 误差，本页给双侧 $L_2$ 尾部误差，不能只按名字互换。

Heavy hitters 恢复 ​

点查询只在给定键时估计。若要从巨大宇宙中找 heavy hitters，需候选生成机制，例如按键位建立分层 CountSketch、递归识别高能桶，再对候选精查。扫描整个宇宙虽正确，却把查询时间变成 $O(U)$，违背流式目标。

误差中 $\Vert f_{-i}{\Vert }_2$ 可进一步用去掉若干最大频率后的 tail norm 表达，支撑 sparse recovery。具体桶数、行数和候选阈值要随 theorem 版本一致，不能把点查询式直接称完整 heavy-hitter 算法。

中位数为什么不可省 ​

对固定 $i$，一行经符号还原后的估计为

符号独立使交叉项期望为零，方差约为 $\Vert f_{-i}{\Vert }_2^2/w$。单行有常数概率落在 $O(\Vert f_{-i}{\Vert }_2/\sqrt{w})$ 内；多行取中位数把失败概率指数压低。取平均虽仍无偏，却会让一行极端碰撞直接拉动结果，不能沿用同一尾界。

更新可正可负且摘要线性，故适合 turnstile 流。恢复 heavy hitters 时，点查询只是验证工具：还要有候选生成、层级哈希或编码机制找到可能的大坐标；遍历整个宇宙逐项查询会把子线性空间优势变成 $\mathrm{\Theta }(U)$ 时间。