admin管理员组

文章数量:1658730

文章目录

  • Count-Min (CM) Sketch
  • Conservative-Update (CU) Sketch
  • Count 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

本文标签： 常见简介sketch

版权声明：本文标题：常见sketch简介 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1729813080a1213564.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。