数据流检测及研究论文

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

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

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

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

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

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

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

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

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

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

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

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

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

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

该sketch具有以下优点：

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

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

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个字存储。