论文阅读:一个改进的数据流摘要:计数-最小草图及其应用。

CM sketch允许快速响应数据流汇总中的基本查询(如点、范围和内积查询)，还可以用来解决数据流中的几个重要问题，如寻找分位数和公共项。

使用CM草图解决这些问题表明，时间和空间范围显著改善了以前已知的问题，通常从到。

我们考虑一个向量，它以隐式和增量的方式呈现。这个向量的维数是n，它在时间t的当前状态是:

最初，a是一个零向量，所有的I。

向量的单个条目的更新以流的形式呈现，t更新是，这意味着:

一般的意思是只修改向量中的一个维度，不改变其他维度。

在最近的数据流方案中，数据流上下文中的函数计算算法需要满足以下要求:

近年来，在数据流的上下文中已经提出了几种不同的草图，它们允许许多简单集合函数的近似。

到目前为止设计的草图通常是其输入的线性函数，可以表示为基本向量的投影，用一些随机选取的投影矩阵来表示数据。

这意味着，通过将这些函数转换为草图上的计算，可以很容易地通过分布在站点上的数据上的一些函数来计算一些函数。因此，它们也适用于分布式应用程序。

虽然草图已经被证明是强大的，但是它们有以下缺点:

鉴于数据流领域由高性能监控应用驱动的事实，例如用于监控IP分组流的数据流算法的响应时间要求，这些缺点最终限制了许多已知数据流算法在适当应用中的使用。

我们将通过提出一种新的草图构造来解决所有这些问题，我们称之为Count-Min或CM草图。

该草图具有以下优点:

在任意时刻t，查询需要在a(t)上计算一些特定的函数:

这些查询对于数据流算法中的许多应用是必要的，并且已经被广泛研究。

Count-Min或CM sketch是根据用于回答点查询的两个基本操作命名的。先计数，再计算最小值。我们用e来表示自然对数函数ln的底部。

带有参数(ε，δ)的Count-Min(CM)草图由宽度为w、深度为d的二维数组Count表示:count [1，1]...计数[d，w]。

然后我们设置参数，还有w和d。

数组的每一项开始都是零。此外，D哈希函数H1...高清:{1...n} → {1...w}是从成对独立的家族中随机均匀选择的。

当更新到达时，这意味着该项目由数字更新，然后添加到每一行的计数中，计数器由确定。

正式设置:

Count-Min草图中使用的空间是一个wd顺序的数组，需要wd字和D hash函数。当使用参考文献中描述的成对函数时，每个散列函数可以存储在2个字中。