概要数据结构（Sketch）

概念

概要数据结构（Sketch）包含H个长度为P的哈希表.

将网络流量数据建模为 （键，值） 的形式， 其中 “键” 为一个或多个数据包头中的字段， 例如源地址或源地址个目的地址的组合， “值”为存储的特征， 例如数据包的数量。

在Sketch中， 每个块表示为 $T[i][j],i=1,2,...,H,j=1,2,...,P,$ 每一行$i$都关联着一个哈希函数$h_i$, 该函数将输入的键映射到哈希空间$（1,2,...,P)$ 中。

例如， 当一个新的数据（key， value）到达时， key将被$h_1,h_2,...,h_H$哈希$H$次，并将值添加到每行对应的块中， 即 $T[i][h_i(key)]+=value,i=1,2,...H$. 进行H次哈希运算的目的是为了避免不同键之间的哈希碰撞。 如果哈希函数是从一个哈希族中选择的。
那么两个不同键被哈希到同一个块中的概率是被限定的。通常， Sketch中所用的$H$个哈希函数是从k-全域哈希函数族中选择的，即

$h(x)={\sum }_{i=0}^{k?1}(a_i{x}^i+b_i)modrmodP$

其中， $r$ 是任意的质数， $a_i(?=0)$ 和 $b_i$是从$(0,1,...,r?1)$中随机选择的数，$P$是Sketch每一列的块数。 通过使用$k?$全域哈希函数， 两个不同键被哈希到同一个块中的概率为$(1/P{)}^{k\times H}$。

具有常数级的查询时间复杂度。