Count–Min Sketch

结构与更新 ​

取宽度 $w$、深度 $d$，每行独立哈希 $h_j:[U]\to [w]$。更新 $(i,\mathrm{\Delta })$ 时对所有行执行

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

点查询返回 ${\hat{f}}_i=\underset{j}{min}C[j,h_j(i)]$。矩阵对频率向量是线性的，但取最小的估计步骤不是线性映射。

一侧误差证明 ​

在 insertion-only 非负流中，每桶为 $f_i$ 加其他碰撞项，所以永不低估。固定一行的噪声期望至多 $\Vert f_{-i}{\Vert }_1/w$；取 $w=\lceil e/\epsilon \rceil$，由Markov 不等式公理库Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。噪声超过 $\epsilon \Vert f{\Vert }_1$ 的概率至多常数。$d=\lceil \ln \left(1/\delta \right)\rceil$ 行独立且取最小，使所有行都坏的概率至多 $\delta$：

$$f_i\le {\hat{f}}_i\le f_i+\epsilon \Vert f{\Vert }_1.$$

频率查询例子 ​

统计 API 路径请求量时，每次请求把对应键加一。冷门路径可能因热门路径碰撞被高估，但多行中只要一行避开主要碰撞，最小值就恢复较小误差；结构不会把真实请求数估得更低。

边界与保证类型 ​

误差是全局 $L_1$ 的加性误差，不是相对误差 $\epsilon f_i$。严格 turnstile 的负更新会让碰撞项可正可负，破坏“只高估”和 min 逻辑；需其他 sketch。哈希独立性、一次固定查询与许多自适应查询的失败概率不同。conservative update 是工程变体，不能沿用所有原始线性性质。

合并与范围聚合 ​

使用相同 $d,w$ 和同一组哈希函数的两个 sketch 可逐计数器相加，得到串接两条流的 sketch；函数不同则桶语义不一致，不能合并。这个性质来自每行计数的线性更新。

若键有顺序，不能直接从单个 CMS 回答任意范围和，因为哈希打散顺序；可在 dyadic interval 层级各维护 sketch，把范围分解成 $O(\log U)$ 个节点，但误差与失败概率也要跨节点累积。

从固定查询到查询集合 ​

上述概率界先固定一个键 $i$。若系统预先知道要同时保证 $q$ 个键，可把单键失败率设为 $\delta /q$，即把深度增至 $d=\lceil \ln \left(q/\delta \right)\rceil$，再用 union bound 得到整组查询共同成功的概率至少 $1-\delta$。查询由先前答案自适应生成时，这个直接换参并不自动成立。

计数器还要按流总质量选择位宽。若使用饱和整数，热门桶到上限后便不再是频率向量的线性映射；若发生无符号回绕，min 甚至可能严重低估。工程实现必须把溢出策略作为误差模型的一部分，而不是把它归入哈希碰撞误差。

CMS 只提供候选键的点估计，不会自行列出 heavy hitters。若宇宙很大，仍需 Misra–Gries、分层编码或外部候选生成器；对全宇宙逐键查询虽正确，却要 $\mathrm{\Theta }(Ud)$ 时间。

参考资料

• Graham Cormode, S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and Its Applications, J. Algorithms, 2005.
• Graham Cormode, Ke Yi, Small Summaries for Big Data, Cambridge University Press, 2020.