论文阅读：An Improved Data Stream Sum

摘要：

本文引入了一种新的亚线性空间数据结构Count-Min Sketch，用于汇总数据流。

CM sketch允许对数据流汇总中的基本查询（例如点，范围和内积查询）进行快速响应，还可以用于解决数据流中的几个重要问题，例如查找分位数，常见项目等。

使用CM sketch解决这些问题所显示的时间和空间范围显着改善了以前已知的问题，通常从 至。

背景/问题：

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

最初，a是零向量，所有i的。

向量的单个条目的更新以成对流的形式呈现，第t次更新为，这意味着:

并且对于所有
都有

在任何时间t，查询都需要计算a（t）上的某些特定功能。

大概意思就是只修改向量中的某一个维，而不改变其他维度。

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

• 首先，算法使用的空间应该很小，最多为n的多对数，即显式表示所需的空间。
• 其次，处理更新应该快速简单，对给定类型的查询的回答应快速并且具有可用的准确性保证。

近年来，已经在数据流上下文中提出了几种不同的sketch，这些sketch允许近似许多简单的聚合函数。

到目前为止设计的sketch通常是其输入的线性函数，并且可以表示为基础向量的投影，向量表示具有某些随机选择的投影矩阵的数据。

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

尽管sketch已被证明功能强大，但它们具有以下缺点：

• 尽管sketch使用的空间很小，使用的空间通常具有Ω（1 /ε2）乘数，ε= 0.1或0.01也非常合理，但是该因素在空间上被证明是昂贵的
• 许多sketch构造需要线性的时间来处理对基础数据的每次更新，sketch通常从几千字节到一兆字节左右，并且每次更新都要处理这么多数据，严重限制了更新速度。
• 使用具有强大独立性保证的散列函数来构造sketch，评估起来可能很复杂，尤其是对于硬件实现而言。
• 文献中描述的许多sketch适用于单个预先指定的聚合计算，鉴于在数据流应用程序中通常会监视同一流上的多个聚合，因此这就要求使用许多不同类型的sketch，这是一个过高的开销

鉴于数据流的领域是由极高性能的监视应用程序驱动的，例如，监视IP数据包流的数据流算法的响应时间要求，而上述的这些缺点最终限制了许多已知数据流算法的使用在合适的应用中。

解决办法：

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

该sketch具有以下优点：

• 使用的空间与1 /ε成正比
• 更新时间在sketch的大小上明显次线性
• 只需要构造简单的成对独立哈希函数
• 该sketch可用于几个不同的查询和多个应用程序
• 使所有常数显式且较小

在任何时间t，查询都需要计算a（t）上的某些特定功能：

• Q（i）的点查询将返回ai的近似值。
• 范围查询Q（l，r）近似为
• Q（a，b）表示为内部乘积近似查询

这些查询是数据流算法中许多应用程序所必需的，并且已经进行了广泛的研究。

CM sketch具体实现：

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

参数为（ε，δ）的Count-Min（CM）草图由宽度为w且深度为d的二维数组计数表示：count [1，1]……count [d，w]。

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

数组的每个条目最初都是零， 此外，再从成对独立的族中随机地均匀选择d个哈希函数h1 ... hd：{1 ... n}→{1 ... w}。

当更新到达时，意味着项被更新了数量，然后被添加到每一行的一个计数中，计数器由确定.

形式上，设置:

Count-Min草图使用的空间是wd数量级的数组，该数组需要wd个字和d散列函数，使用参考文献中所述的成对函数时，每个散列函数都可以使用2个字存储。