Count-Min Sketch

定义

Count-Min Sketch 由 Cormode 和 Muthukrishnan 于 2005 年提出,是一种流式频率估计的概率数据结构:用远小于元素种类数的空间,近似回答"某元素出现了多少次"。

原理

结构是一个 d 行 w 列的计数器矩阵,每行配一个独立哈希函数。元素到来时,在每一行把它哈希到的那个计数器加一;查询时取 d 行对应计数器的最小值作为估计。由于哈希冲突只会让计数器偏大,估计值永远不小于真实值,且以 1-delta 的概率误差不超过 epsilon 乘以流总量,其中 w 约为 e/epsilon、d 约为 ln(1/delta)。

应用

用于网络流量测量中的大流(heavy hitter)检测、搜索热词与商品热度统计、数据库查询优化器的频率估计、CDN 与缓存系统(如 Caffeine 缓存的 TinyLFU 准入策略用其变体记录访问频率)等大数据流场景。

优缺点

优点是空间与元素种类数无关、更新查询均 O(d)、天然支持分布式合并(矩阵逐项相加);缺点是只会高估、低频元素相对误差大,不支持列出所有元素。