大数据流的在线Heavy Hitters算法（下篇）：基于略图的

Continue...

之前有好几篇分上下篇写的文章都鸽了，惭愧惭愧。为了不食言，今天继续聊Heavy Hitters（频繁项）算法之基于略图（Sketch）的方法。时间紧张且限于水平，写得简单些，看官勿怪。

什么是略图

顾名思义，略图（Sketch）就是能够大致准确地描述一份数据集的摘要。当数据量非常大时，往往不能直接放入内存中，普通的查找树、哈希表等受制于数据规模，自然也就没有用武之地了。然而，略图的出现以精准度作为trade-off换来了时间、空间效率的极大提升，也使得解决大数据上的Heavy Hitters以及其他很多问题成为可能。

概率性数据结构（probabilistic data structure）有不少都采用了略图的思想，笔者很久之前讲过的布隆过滤器就是最典型的应用，它可以借助位图与多个哈希函数来非常高效地判断集合中元素的存在性。而本文接下来要讲的两种略图——Count-Min Sketch与Count Sketch——则是解决Heavy Hitters问题的利器，本质上也是布隆过滤器思想的延续。

Count-Min Sketch

Count-Min Sketch的论文发表于2004年，其数据结构由两部分组成：

• 一个宽度为w，深度为d（即d行w列）的二维整数数组，初始化为全0；
• d个互相独立的哈希函数h₁...h_d，其哈希空间均为[1...w]。

接下来观察数据流，当数据流中元素j出现时（可以出现1次，也可以连续出现c次），将j分别用哈希函数h₁...h_d映射到二维数组中每一行的对应位置，并将该位置的值加上c。如下图所示，可以看出，Count-Min Sketch非常类似于扩展到d维并且加上了计数功能的布隆过滤器。

那么如何估计一个元素j的大致出现频率f[j]呢？答案是直接取元素j对应的所有哈希桶中，计数值最小的那一个。即：

f[j] = min_k CMS[k][h_k(j)]

当然，为了保证一定的精准度，w和d的值也不是随便取的。定义精度参数为ε，误差概率参数为δ（两者都是很小的正数），那么就有：

w = 2/ε, d = log 1/δ

ε、δ两个参数之间有如下的关系：

P{ f[j] <= f[j] + ε||f||₁ } >= 1 - δ

翻译成人话：在至少为1 - δ的概率下， Count-Min Sketch对任意一个元素j估计的出现频率与其真实频率的误差小于所有元素真实频率之和的ε倍。这个结论可以用马尔可夫不等式来证明，笔者数学不怎么样，就不班门弄斧了。

容易得知，由于哈希冲突的存在，Count-Min Sketch给出的频率估计肯定是偏大的（即f[j] >= f[j]）。在输入数据量足够多的情况下，选择最小的频率计数值就意味着哈希冲突最少，亦即更接近真实的频率值。反过来，它对于很少出现的元素，表现就会比较差。

话说回来，如何用Count-Min Sketch解决Heavy Hitters问题呢？答案就比较直白了——使用K个元素的最小堆维护Top-K，每更新一个元素的计数，就同时更新到最小堆，并随时移除频率过小的元素。具体操作方法参见笔者之前介绍PriorityQueue的文章的结尾。

Count-Min Sketch在现实中的应用也很广泛。在笔者所知的开源框架里，Spark在spark-sketch子模块中实现了包括Count-Min Sketch在内的多种略图结构，并应用在CountMinSketchAgg聚合函数以及DataFrame的数据统计中。PostgreSQL也有一个Count-Min Sketch插件，专门用于近似计算Top-K。

Count Sketch

Count Sketch的论文发表于2002年，比Count-Min Sketch还要早，本质上是Count-Min Sketch的一般化形式。除了w*d的二维数组和d个哈希函数之外，还有另外一组哈希函数g₁...g_d，且它们的哈希空间只有{1, -1}两个值。另外，g₁...g_d取{1, -1}的分布必须是随机且均匀的，也就是说E[g(j)]=0。

当数据流中元素j出现c次时，将j分别用哈希函数h₁...h_d映射到二维数组中每一行的对应位置，并将该位置的值加上c*g(j)，如下图所示。

g₁...g_d哈希函数是Count Sketch与Count-Min Sketch的最大不同点，它的存在可以部分抹去Count-Min Sketch中的只加操作带来的正误差，因此估算f[j]时不必再取元素j对应的所有哈希桶中计数值最小的那一个了。相对地，我们取中位数，即：

f[j] = median_j CS[k][h_k(j)] * g_k(j)

Count Sketch的ε、δ两个参数与估计误差之间有如下的关系（可以借助切比雪夫不等式证明）：

P{ f[j] - ε||f_-j||₂ <= f[j] <= f[j] + ε||f_-j||₂ } >= 1 - δ

由上可知，Count-Sketch给出的频率估计有可能偏大也有可能偏小，但是它用更多的空间（w ~ O(1/ε²)）换来了比Count-Min Sketch更严格的误差界限。

使用Count Sketch解决Heavy Hitters问题的思路与Count-Min Sketch相同，就不再赘述了。

The End

还有一大堆其他的事情要搞，晚安吧各位。