常见sketch简介
假设我们有一个数据包序列 S = { p 1 , p 2 , ⋯ , p n } \mathrm{S}=\{p_1, p_2, \cdots, p_n\} S={p1,p2,⋯,pn}. h 1 ( . ) , h 2 ( . ) , ⋯ , h d ( . ) h_1(.), h_2(.), \cdots, h_d(.) h1(.),h2(.),⋯,hd(.)均为哈希函数. 对于任意一个数据包 p i p_i pi, 假设它的流标识符为 i d i id_i idi, 则 h j ( i d i ) h_j(id_i) hj(idi)将生成一个随机数, 其中 i = 1 , 2 , ⋯ , n . j = 1 , 2 , ⋯ , d . i=1,2,\cdots, n. j = 1, 2, \cdots, d. i=1,2,⋯,n.j=1,2,⋯,d. 我们将以这一场景来介绍以下的几种sketch.
Count-Min (CM) Sketch
G. Cormode and S. Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and Its Applications,” in LATIN 2004: Theoretical Informatics, Apr. 2004, pp. 29–38, doi: 10.1007/978-3-540-24698-5_7.
我们首先建立 d d d个哈希表, 每个哈希表包含 w w w个哈希桶, 每个哈希桶都是一个计数器. 当一个数据包 p i p_i pi到达的时候, 我们从它的流标识符 i d i id_i idi生成 d d d个不同的索引值, 即 i d x 1 = h 1 ( i d i ) , i d x 2 = h 2 ( i d i ) , ⋯ , i d x d = h d ( i d i ) idx_1 = h_1(id_i), idx_2=h_2(id_i), \cdots, idx_d=h_d(id_i) idx1=h1(idi),idx2=h2(idi),⋯,idxd=hd(idi). 每个索引都分别在一个哈希表确定了一个唯一的哈希桶. 随后, 我们将每个哈希表中刚才确定的哈希桶的计数值增加1, 于是便完成了这个数据包对Count-Min Sketch的更新.
# 假设d=3, 单个哈希表的宽度为w
哈希表1 = [0]*w
哈希表2 = [0]*w
哈希表3 = [0]*w
def CountMin(数据包):
标识符 = 数据包.流标识符
索引1 = h1(标识符)%w
索引2 = h2(标识符)%w
索引3 = h3(标识符)%w
哈希表1[索引1] += 1
哈希表2[索引2] += 1
哈希表3[索引3] += 1
当我们要查询某个数据流 f i f_i fi的长度的时候, 我们首先提取这个数据流的流标识符 i d i id_i idi, 然后使用 h 1 ( . ) , h 2 ( . ) , ⋯ , h d ( . ) h_1(.), h_2(.), \cdots, h_d(.) h1(.),h2(.),⋯,hd(.)分别在每个哈希表中确定一个哈希桶, 这 d d d个哈希桶中的最小计数值便是对数据流 f i f_i fi的长度的估计.
def 查询(f):
标识符 = f.流标识符
索引1 = h1(标识符)%w
索引2 = h2(标识符)%w
索引3 = h3(标识符)%w
长度 = min(哈希表1[索引1], 哈希表2[索引2], 哈希表3[索引3])
return 长度
Conservative-Update (CU) Sketch
C. Estan and G. Varghese, “New directions in traffic measurement and accounting,” in Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, Pittsburgh, Pennsylvania, USA, Aug. 2002, pp. 323–336, doi: 10.1145/633025.633056.
我们同样创建 d d d个哈希表, 每个哈希表的宽度为 w w w, 每个哈希桶都仅包含一个计数器. 当一个数据包到达的时候, 我们用 h 1 ( . ) , h 2 ( . ) , ⋯ , h d ( . ) h_1(.), h_2(.), \cdots, h_d(.) h1(.),h2(.),⋯,hd(.)对数据包的流标识符进行哈希, 从而在每个哈希表中确定唯一的一个哈希桶. 现在我们已经找到了 d d d个计数器; 我们将具有最小计数值的计数器增加1. 这个计数器更新后有计数值 c c c, 则对于剩余的计数器, 如果他们的值小于 c c c, 则我们将它们的值都设为 c c c, 否则就保持它们的值不变.
# 假设d=3, 单个哈希表的宽度为w
哈希表1 = [0]*w
哈希表2 = [0]*w
哈希表3 = [0]*w
def ConservativeUpdate(数据包):
标识符 = 数据包.流标识符
索引1 = h1(标识符)%w
索引2 = h2(标识符)%w
索引3 = h3(标识符)%w
最小计数值 = min(哈希表1[索引1], 哈希表2[索引2], 哈希表3[索引3]) + 1
哈希表1[索引1] = max(哈希表1[索引1], 最小计数值)
哈希表2[索引2] = max(哈希表2[索引2], 最小计数值)
哈希表3[索引3] = max(哈希表3[索引3], 最小计数值)
向Conservative-Update Sketch查询数据流 f f f的长度的时候, 我们依然对 f f f的流标识符进行哈希, 从而在每个哈希表中确定一个哈希桶, 这些哈希桶的最小计数值就是Conservative-Update Sketch对数据流 f f f的长度的估计.
def 查询(f):
标识符 = f.流标识符
索引1 = h1(标识符)%w
索引2 = h2(标识符)%w
索引3 = h3(标识符)%w
长度 = min(哈希表1[索引1], 哈希表2[索引2], 哈希表3[索引3])
return 长度
Count Sketch
M. Charikar, K. Chen, and M. Farach-Colton, “Finding Frequent Items in Data Streams,” in Automata, Languages and Programming, Berlin, Heidelberg, 2002, pp. 693–703, doi: 10.1007/3-540-45465-9_59.
我们同样有 d d d个哈希表, 每个哈希表包含 w w w个计数器. 但是现在我们有两组哈希函数, 其中 h 1 ( . ) , h 2 ( . ) , ⋯ , h d ( . ) h_1(.), h_2(.), \cdots, h_d(.) h1(.),h2(.),⋯,hd(.)可以由一个流标识符生成一个索引, 而 s 1 ( . ) , s 2 ( . ) , ⋯ , s d ( . ) s_1(.), s_2(.), \cdots, s_d(.) s1(.),s2(.),⋯,sd(.)可以由一个流标识符随机生成 { + 1 , − 1 } \{+1, -1\} {+1,−1}中的一个数. 当一个数据包 p i p_i pi到达的时候, 我们会由它的流标识符生成一个索引 i d x j = h j ( p i . 流 标 识 符 ) idx_j=h_j(p_i.流标识符) idxj=hj(pi.流标识符), 然后将第 j j j个哈希表中于 i d x j idx_j idxj对应的计数器的值加上 s j ( p i . 流 标 识 符 ) s_j(p_i.流标识符) sj(pi.流标识符). 具体更新算法如下:
# 假设d=3, 单个哈希表的宽度为w
哈希表1 = [0]*w
哈希表2 = [0]*w
哈希表3 = [0]*w
def CountSketch(数据包):
标识符 = 数据包.流标识符
索引1 = h1(标识符)%w
索引2 = h2(标识符)%w
索引3 = h3(标识符)%w
哈希表1[索引1] += s1(标识符)
哈希表2[索引2] += s2(标识符)
哈希表3[索引3] += s3(标识符)
当我们要查询某个数据流 f f f的长度的时候, 我们根据 f f f的长度从每个哈希表中确定一个计数值, 然后求他们的中位数, 所得结果即为CountSketch对数据流 f f f的长度的估计.
def 查询(f):
标识符 = f.流标识符
索引1 = h1(标识符)%w
索引2 = h2(标识符)%w
索引3 = h3(标识符)%w
长度 = 中位数(哈希表1[索引1]*s1(标识符), 哈希表2[索引2]*s2(标识符), 哈希表3[索引3]*s3(标识符))
return 长度