d 行计数矩阵 · 单边误差 · 界 ε·N

Count-Min Sketch：只会高估的频次表

HyperLogLog 数的是「有多少个不同的 key」，Count-Min Sketch 数的是「某个特定的 key 出现了多少次」。后一个问题的精确答法是一张 Map，内存与不同 key 的个数同阶。

Count-Min 用一个固定大小的整数矩阵顶替这张 Map。它的误差有一个别处少见的性质：单边。估计值永远不小于真值，永远不会报少。这条性质不是概率意义上的，是每一次查询都成立的硬不变量，可以逐元素断言。

1 · 计数矩阵与取最小值

结构是 $d$ 行 $\times$ $w$ 列的计数矩阵，第 $r$ 行配一个独立的散列函数 $h_r : \text{key} \to [0, w)$ 。

add(k, c)：对每一行，把 $(r, h_r(k))$ 这个格子加 $c$ 。
estimate(k)：取这 $d$ 个格子的最小值。

定义 1.1（Count-Min 估计） 设矩阵为 $C$ ，则 $\hat{f}(k) = \min_{0 \le r < d} C[r][h_r(k)]$ 。

每个格子里装的是「落进本格的所有 key 的频次之和」。被查的 key 自己那一份一定在里面，别的 key 只会往上叠，所以每个格子都不小于真值，取最小值仍不小于真值。

定理 1.2（单边性） 对任意 key $k$ 与任意时刻， $\hat{f}(k) \ge f(k)$ 。

证明固定行 $r$ 。 $C[r][h_r(k)] = \sum_{k' : h_r(k') = h_r(k)} f(k')$ ，右端的求和至少含 $f(k)$ 这一项，其余各项非负。故每一行的格子都不小于 $f(k)$ ，最小值亦然。∎

图 1-1 · 一个

d

行

w

列的计数矩阵与一次查询。蓝框是被查 key 在每行命中的格子，绿框是取到的最小值。可调

w

、

d

与流长，可点选不同的 key 观察高估量的变化。

2 · 参数的两个方向

误差界的形式是「以概率 $1 - \delta$ ，高估量不超过 $\varepsilon N$ 」，其中 $N$ 是已计入的总频次。给定目标 $(\varepsilon, \delta)$ ，参数取

w = \left\lceil \frac{e}{\varepsilon} \right\rceil, \qquad d = \left\lceil \ln \frac{1}{\delta} \right\rceil

两个参数管的事不同。 $w$ 管幅度：单行的期望污染量是 $N/w$ ，取 $w = e/\varepsilon$ 让它落在 $\varepsilon N / e$ 。 $d$ 管运气：单行超出 $\varepsilon N$ 的概率不超过 $1/e$ ， $d$ 行同时超出的概率不超过 $e^{-d}$ 。

取 $\varepsilon = 0.001$ 、 $\delta = 0.01$ 得 $w = 2719$ 、 $d = 5$ ，矩阵 13595 格。每格 4 字节共 54380 字节，与流有多长、有多少个不同 key 都无关。

注 · 两个参数在内存上的地位不对称。 $w$ 与 $1/\varepsilon$ 成正比，精度提高十倍要多花十倍内存； $d$ 只与 $\ln(1/\delta)$ 成正比，把失败概率从 1% 压到 0.01% 只需从 5 行加到 10 行。想省内存先砍 $d$ 是走反了方向。

3 · 高估量与流长的关系

误差界写的是 $\varepsilon N$ ，不是 $\varepsilon \times$ 不同 key 的个数。实测把这一点摆得很清楚： $w = 2719$ 、 $d = 5$ 、zipf(1.1) 词表 10 万，流长从 1 万涨到 100 万时不同 key 只从 3108 涨到 64724（20 倍），而平均高估量从 0.17 涨到 60.76（357 倍），几乎正比于流长。

流长 $N$	不同 key	平均高估	最大高估	理论界 $\varepsilon N$
10000	3108	0.17	3	10.0
100000	17104	5.27	34	100.0
400000	41163	23.82	127	399.9
1000000	64724	60.76	328	999.7

污染量是「别的 key 落进同一格的频次之和」，与它们有多少种无关。最大高估始终只用掉理论界的三分之一左右，界是宽松的。

图 3-1 · 高估量随流长的增长，以及与理论界

\\varepsilon N

的距离。可在平均与最大之间切换纵轴，可开关理论界那条参考线。

真正的代价落在低频 key 上。绝对高估量对所有 key 是同一个量级，于是真实频次只有个位数的 key，在 $N = 10^6$ 时被高估几十，相对误差上千个百分点。Count-Min 适合回答「热 key 有多热」，不适合回答「这个冷 key 到底出现过几次」。

4 · conservative update

普通 update 把 $d$ 个格子各加 1，其中含一处浪费：某个格子已经明显高于其余几个时，把它再抬高不会改变 $\min$ ，只会污染别的 key。

conservative update 去掉这一步浪费：先算出这 $d$ 个格子的当前最小值 $\text{min}$ ，然后只把小于 $\text{min} + 1$ 的格子抬到 $\text{min} + 1$ ，已经更高的一动不动。被查 key 的估计值照样每次涨 1，单边性不破。

图 4-1 · 同一条流喂给两个矩阵，上下对照普通 update 与 conservative update 的写入量。可调

w

、

d

与流长，可点选不同 key 比较两侧的估计。

实测同一组参数下 conservative update 把平均高估量从 60.76 压到 32.78，最大高估从 328 压到 238。恰好命中真值的 key 比例从 0.0% 升到 1.5%。这是一处几乎免费的改良，代价只在合并上。

5 · 可合并性

普通 Count-Min 的合并是逐格相加，结果与把两条流拼起来建一个 sketch 逐格相等。理由与 HyperLogLog 那边同构：格子里存的量本身可加，合并只是把两个和加起来。这一条可以逐格断言。

6 · conservative update 在合并上的代价

conservative update 的合并语义要分三句话说清，含糊的说法（「不可合并」）会误导。 $w = 256$ 、 $d = 4$ 、两批各 2 万条 zipf 流的实测：

做法	平均高估	最大高估	低估的 key 数
普通 · 直接建	42.90	193	0
普通 · 逐格相加	42.90	193	0
conservative · 直接建	22.25	119	0
conservative · 逐格相加	22.96	119	0
conservative · 逐格取 max	5.56	66	275

第一句：普通版逐格相加与直接建逐格相等，两行数字一模一样，不是巧合。

第二句：conservative 版逐格相加仍不低估（每个格子都不小于落在它上面的任一 key 的频次，两个不小于相加还是不小于），但结果不再逐格等于对合并后的流跑一遍——平均高估 22.96 对 22.25，两个矩阵逐格不等。合并后的那份也不再是一个 conservative sketch，继续往里 add 会得到更差的估计。

第三句是陷阱所在。逐格取 max 看着更紧，平均高估只有 5.56，但 2803 个 key 里有 275 个被报低了，最大低估 2214。单边性就此破掉，而这个错误在小规模测试里很容易漏过去：低估的都是低频 key，热 key 的估计看着照样正确。

警示 · 上表的最后一行最初是作为「CU 不可合并」的反例写的，实测后发现取 max 对普通版同样低估（同一组数据 133 个 key，最大低估 2195）。问题不在 conservative update，在 max 这个算子：格子里存的是和不是极值，取 max 会丢掉另一份里的那部分计数。HyperLogLog 逐桶取 max 成立，恰恰因为它的桶里存的就是极值。

7 · 参考文献

Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58–75.
Estan, C., & Varghese, G. (2002). New directions in traffic measurement and accounting. SIGCOMM 2002, 323–336.
Goyal, A., Daumé III, H., & Cormode, G. (2012). Sketch algorithms for estimating point queries in NLP. EMNLP-CoNLL 2012, 1093–1103.
Cormode, G., & Yi, K. (2020). Small Summaries for Big Data. Cambridge University Press，第 3 章。