CountSketch

线性摘要 ​

每行选择桶哈希 $h_j:[U]\to [w]$ 与独立符号哈希 $s_j:[U]\to \{-1,+1\}$。更新 $(i,\mathrm{\Delta })$ 时

$$C[j,h_j(i)]+=s_j(i)\mathrm{\Delta }.$$

第 $j$ 行对 $i$ 的估计为 $X_j=s_j(i)C[j,h_j(i)]$，最终取各行中位数。

无偏与方差 ​

展开得

$$X_j=f_i+\sum _{k\ne i:h_j(k)=h_j(i)}{s}_j(i)s_j(k)f_k.$$

随机符号使交叉噪声期望为零；配合桶碰撞概率，方差受 $\Vert f_{-i}{\Vert }_2^2/w$ 控制。选择 $w=\mathrm{\Theta }(1/{\epsilon }^2)$ 可让单行以常数概率误差不超过 $O(\epsilon \Vert f_{-i}{\Vert }_2)$，再用 $d=\mathrm{\Theta }(\log \left(1/\delta \right))$ 行的中位数提升置信度。

正负碰撞例子 ​

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$，一行经符号还原后的估计为

$$f_i+\sum _{x\ne i:h(x)=h(i)}s(i)s(x)f_x.$$

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

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

参考资料

• Moses Charikar, Kevin Chen, Martin Farach-Colton, Finding Frequent Items in Data Streams, ICALP, 2002.
• Piotr Indyk, Stable Distributions, Pseudorandom Generators, Embeddings, and Data Stream Computation, JACM, 2006.