概要数据结构（Sketch）

概念

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

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

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

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

h ( x ) = ∑ i = 0 k − 1 ( a i x i + b i ) m o d r m o d P h(x) =sum_{i=0}^{k-1}(a_ix^i+b_i)modrmodP h(x)=∑i=0k−1(aixi+bi)modrmodP

其中， r r r 是任意的质数， a i ( ≠ 0 ) a_i( eq 0) ai(=0) 和 b i b_i bi是从 ( 0 , 1 , . . . , r − 1 ) (0,1,...,r-1) (0,1,...,r−1)中随机选择的数， P P P是Sketch每一列的块数。 通过使用 k − k- k−全域哈希函数， 两个不同键被哈希到同一个块中的概率为 ( 1 / P ) k × H (1/P)^{k imes H} (1/P)k×H。

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

复杂度：O(1) - O(n)