Sketch算法-CM Sketch、Count Sketch等
姜俊逸
sketch统计网络数据流中某个元素出现的频率，反应数据流的特征。并不实际的存储数据流中的元素，只存储他们的计数。
基本原理是数组每个单元维持一个计数器，当数据流的元素哈希索引到数组的某个位置，此位置计算器加一。查询某个元素的出现频率只需哈希索引到对应计数器即可。很明显，由于不同元素可能索引到同一个位置，这种方法得到的计数值一般是偏大的。
Count Sketch
运行sketch方法k次，每次对应单独的哈希函数h（索引到数组某个位置）和g（哈希函数g的目的是无偏估计），然后取结果的平均值。
CM Sketch
Count-Min Sketch算法进行更进一步的优化，维持一个二维数组，用k个哈希索引（二维数组有k行），类似布隆过滤器。对每个元素进行k次哈希索引到每行相应的位置并使该位置计数器加一。查询时同样进行k次哈希，并取k个计数器中的最小值。
类似资料：