Count–Min Sketch

每一行都把目标频率与碰撞噪声加在同一个桶里；在非负流中噪声只能向上推高估计。多行独立哈希后取最小值，相当于等待至少一行避开严重碰撞，因此保留“不低估”的方向并把同时坏掉的概率指数压低。

Count–Min 对非负频率使用无符号桶和逐行最小值，碰撞只会造成单边高估；CountSketch理路CountSketchCountSketch · Count Sketch以桶哈希和随机符号抵消碰撞，再跨行取中位数估计频率与 L2 heavy hitters。加入随机符号并取中位数，误差围绕真实频率摆动，更适合 turnstile 流和 ${\ell }_2$ 尾部保证。

频率查询例子 ​

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

边界与保证类型 ​

误差是全局 $L_1$ 的加性误差，不是相对误差 $\epsilon f_i$。Strict turnstile 允许负更新，但每个当前频率仍非负：碰撞键先 $+3$ 再 $-2$，对桶的净贡献是 $+1$，不会破坏单边高估。一般 turnstile 允许负频率；若目标频率为 $2$，某碰撞键频率为 $-3$，该桶就为 $-1$，取 min 会低估。问题在当前频率的符号，而非更新的符号。哈希独立性、固定查询集合与自适应查询或更新的失败概率约定仍须分别核对。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 · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。得到整组查询共同成功的概率至少 $1-\delta$。查询由先前答案自适应生成时，这个直接换参并不自动成立。

计数器还要按流总质量选择位宽。若使用饱和整数，热门桶到上限后便不再是频率向量的线性映射；若发生无符号回绕，min 甚至可能严重低估。因此要选用足够宽的计数器，或明确报告溢出策略带来的额外误差。

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