5

Count-Min 草图的宽度(桶数)和深度(哈希函数数)决定了检索到的频率估计的准确性。

来自Count-Min 原作者2005 年的论文:

参数 w 和 d 可以通过设置 w=⌈e/ε⌉ 和 d=⌈ln1/δ⌉ 来选择,其中回答查询的误差在 ε 的因子内,概率为 δ。

如上所述:

w=⌈e/error⌉

d=⌈ln(1/(1−certainty))⌉

来自Count-Min 原作者2011 年的论文:

假设我们希望误差最多为 0.1(所有频率之和),确定性为 99.9。那么我们要2/w=1/1000,我们设w=2000,且(1/2)^d=0.001,即d=log0.001/log0.5 ≤ 10。

导致:

w=⌈2/error⌉

d=⌈ln(1−certainty)/ln(1/2)⌉

然而,误差必须取决于存储在草图中的元素总数 N。元素越多,错误和错误概率就越大。为了创建初始草图,什么是合适的功能?

4

0 回答 0