Count-Min Sketch 通过接受单侧误差来计数数据流

数据流使精确计数变得不切实际：为每个可能出现的项保留一个计数器，所需内存可能超过流处理器所拥有的内存。较早的摘要方法改善了空间占用，但许多界限仍然过于昂贵。

Count-Min Sketch 使用一个小型计数器矩阵和多个哈希函数。更新是常数时间的递增操作；点查询、范围查询和内积查询是近似的，但速度快，且内存占用为亚线性。

Cormode 和 Muthukrishnan 的发表页面总结了这一改进：对于若干流问题，空间或时间界限通常从 1/epsilon 的平方这一因子改善到 1/epsilon。

让每一个误差都向上偏

哈希碰撞被容忍而不是被防止，这使得内存固定且可预测。

在各行之间取最小值，将许多有噪声的计数器转化为有界的过高估计。

该结构支持多种流查询，而不仅仅是单次高频项报告。

它小巧、可合并的形态使其在遥测、广告、网络和数据库中都切实可用。

当近似方法的误差具有方向性时，它更容易运维；单侧误差让下游系统可以将结果视为安全的上界估计。

Count-Min Sketch 成为流式系统中频率估计的标准草图之一。其巧妙之处不在于假装碰撞会消失；而是安排碰撞，使其损害可度量且为单侧。