概要数据结构（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,
概念
概要数据结构（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, 每一行iii都关联着一个哈希函数hih_ihi, 该函数将输入的键映射到哈希空间（1,2,...,P)（1,2,...,P)（1,2,...,P) 中。
例如， 当一个新的数据（key， value）到达时， key将被h1,h2,...,hH{h_1, h_2,...,h_H}h1,h2,...,hH哈希HHH次，并将值添加到每行对应的块中， 即 T[i][hi(key)]+=value,i=1,2,...HT[i][h_i(key)]+ = value, i = 1,2,...HT[i][hi(key)]+=value,i=1,2,...H. 进行H次哈希运算的目的是为了避免不同键之间的哈希碰撞。 如果哈希函数是从一个哈希族中选择的。
那么两个不同键被哈希到同一个块中的概率是被限定的。通常， Sketch中所用的HHH个哈希函数是从k-全域哈希函数族中选择的，即
h(x)=∑i=0k−1(aixi+bi)modrmodPh(x) =\sum_{i=0}^{k-1}(a_ix^i+b_i)modrmodPh(x)=∑i=0k−1(aixi+bi)modrmodP
其中， rrr 是任意的质数， ai(≠0)a_i(\neq 0)ai(=0) 和 bib_ibi是从(0,1,...,r−1)(0,1,...,r-1)(0,1,...,r−1)中随机选择的数，PPP是Sketch每一列的块数。 通过使用k−k-k−全域哈希函数， 两个不同键被哈希到同一个块中的概率为(1/P)k×H(1/P)^{k\times H}(1/P)k×H。
具有常数级的查询时间复杂度。
复杂度：O(1) - O(n)
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)