目录
3.1 Sketch 数据的存储
A sketch is composed of H H H hash tables of size M M M
network traffic ⇔ \Leftrightarrow ⇔ (key,value) pairs
each bucket ⇔ \Leftrightarrow ⇔ T [ i ] [ j ] T[i][j] T[i][j], i = 1 , 2 , ⋯ , H i=1,2,\cdots, H i=1,2,⋯,H, j = 1 , 2 , ⋯ , M j=1,2,\cdots, M j=1,2,⋯,M
row i i i independent hash function h i h_i hi ; hashing space ( 1 , 2 , ⋯ , M ) (1,2,\cdots,M) (1,2,⋯,M)
不同于已有的哈希,当有新的键值对进入,这个item ( k e y , v a l u e ) (key,value) (key,value) 将进行H次哈希运算,尽一步避免不同的key之间产生相同的value
其中哈希函数选择为: k − u n i v e r s a l k-universal k−universal (论文中公式一的 x i x^i xi并没有说明,应该就是 x x x)
碰撞概率: 1 M k ∗ H \frac{1}{M}^{k*H} M1k∗H
h ( x ) = ∑ i = 0 k − 1 ( a i x + b i ) m o d r m o d M h(x) = \sum_{i=0}^{k-1}{(a_ix+b_i) \ mod \ r \ mod \ M} h(x)=i=0∑k−1(aix+bi) mod r mod M
3.2 Bloom filter 数据的查询
Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。
计算某元素x是否在一个集合中,首先能想到的方法就是将所有的已知元素保存起来构成一个集合R,然后用元素x跟这些R中的元素一一比较来判断是否存在于集合R中;我们可以采用链表等数据结构来实现。但是,随着集合R中元素的增加,其占用的内存将越来越大。试想,如果有几千万个不同网页需要下载,所需的内存将足以占用掉整个进程的内存地址空间。即使用MD5,UUID这些方法将URL转成固定的短小的字符串,内存占用也是相当巨大的。 于是,我们会想到用Hash table的数据结构,运用一个足够好的Hash函数将一个URL映射到二进制位数组(位图数组)中的某一位。如果该位已经被置为1,那么表示该URL已经存在。
Hash存在一个冲突(碰撞)的问题,用同一个Hash得到的两个URL的值有可能相同。为了减少冲突,我们可以多引入几个Hash,如果通过其中的一个Hash值我们得出某元素不在集合中,那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时,才能确定该元素存在于集合中。这便是Bloom-Filter的基本思想。
一个m位初始元素全部为0的数组,k个独立的哈希函数取值范围是 ( 0 , 1 , … , m − 1 ) (0,1,\dots,m-1) (0,1,…,m−1) ;
一个元素在集合中,其经过哈希函数后讲对应的位置元素值置1;
在查询一个元素时,其key经过哈希若有一位为0,则该key不在集合中
一个元素哈希后全部位都是1,也不代表该元素在该集合中
3.2.1 Bloom Filter的分析
-
一个bloom filter的参数误判率推导
参数 参数说明 m bit数组的宽度(bit数) n 插入其中key的数量 k 使用hash函数的个数 f False Positive的概率 -
错误率的推导
某一位在插入新元素时,没有被置一的概率: 1 − 1 m 1-\frac{1}{m} 1−m1
在k次hash操作后,该位依然没有被置一的概率: ( 1 − 1 m ) k (1-\frac{1}{m})^k (1−m1)k
在插入n个元素,该位依然没有被置一的概率: ( 1 − 1 m ) n k (1-\frac{1}{m})^{nk} (1−m1)nk, 该位为1的概率: 1 − ( 1 − 1 m ) n k 1-(1-\frac{1}{m})^{nk} 1−(1−m1)nk
当要查询一个新的元素是否在集合中,该元素不在集合中,但经过k次hash其k位置全部被置一的概率: ( 1 − ( 1 − 1 m ) n k ) k (1-(1-\frac{1}{m})^{nk})^k (1−(1−m1)nk)k;
根据极限公式: l i m x → ∞ ( 1 − 1 x ) − x = e lim_{x\to\infty}(1-\frac{1}{x})^{-x}=e limx→∞(1−x1)−x=e
错误率 f = ( 1 − ( 1 − 1 m ) n k ) k ≈ ( 1 − e − k n m ) k f= (1-(1-\frac{1}{m})^{nk})^k \approx (1-{e^{-\frac{kn}{m}}})^k f=(1−(1−m1)nk)k≈(1−e−mkn)k
从上式可以看出,当m 增大时,误判率减小;当n增大时,误判率增大。
-
最佳哈希函数 k k k 的选择
f ( k ) = ( 1 − e − k n m ) k , k ≥ 1 f(k)=(1-{e^{-\frac{kn}{m}}})^k, k\geq1 f(k)=(1−e−mkn)k,k≥1
令 b = e n m b = e^{\frac{n}{m}} b=emn 其中 0 ≤ n ≤ m 0 \leq n\leq m 0≤n≤m ,故 1 ≤ b ≤ e 1 \leq b \leq e 1≤b≤e,故 ( 1 b ) ≤ 1 (\frac{1}{b}) \leq 1 (b1)≤1
f ( k ) = [ 1 − ( 1 b ) k ] k f(k)=[1-(\frac{1}{b})^k]^k f(k)=[1−(b1)k]k;易得该函数为减函数
当 f ( k ) f(k) f(k)导数取0,取得误码率的最小值
f ( k ) = [ 1 − ( 1 b ) k ] k ( 1 ) f(k)=[1-(\frac{1}{b})^k]^k \qquad (1) f(k)=[1−(b1)k]k(1)
公式(1)两边取对数得: l n f ( k ) = k l n ( 1 − ( 1 b ) k ) ( 2 ) lnf(k)=kln(1-(\frac{1}{b})^k) \qquad (2) lnf(k)=kln(1−(b1)k)(2)
公式(2)两边对k求导得: 1 f ( k ) ⋅ f ˙ ( k ) = l n ( 1 − ( 1 b ) k ) + k b − k l n b 1 − b − k ( 3 ) \frac{1}{f(k)} \cdot \dot f(k) = ln(1-(\frac{1}{b})^k) + \frac{kb^{-k}lnb}{1-b^{-k}} \qquad (3) f(k)1⋅f˙(k)=ln(1−(b1)k)+1−b−kkb−klnb(3)
若 f ( k ) f(k) f(k)取最值,则 f ( k ) ˙ = 0 \dot{f(k)}=0 f(k)˙=0 ,带入公式(3)得:
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ & ln(1-(\frac{…当 k = 0.7 ⋅ m n k=0.7\cdot \frac{m}{n} k=0.7⋅nm时,错误率最小,k为最佳哈希函数个数;误判率为:
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P(error)=f(k) … -
Bloom Filter内存的==占用分析==
实际使用中,往往是在保证误判率P和确定元素个数n,分析过滤器的内存占用情况
已知在最佳哈希函数的情况下,误判率:$P(error)=f(k) =2^{-ln2 \cdot \frac{m}{n}} $
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P & = 2^{-ln2\…在哈希函数个数k最优时( k = l n 2 m n k=ln2\frac{m}{n} k=ln2nm): P ( e r r o r ) = 2 − l n 2 ⋅ m n = 2 − k P(error)=2^{-ln2\cdot\frac{m}{n}}=2^{-k} P(error)=2−ln2⋅nm=2−k
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ & P(error) =2^…
也就是说,在错误率 P = 1 % P=1\% P=1%,存储一个元素需要 m n = 1.44 ⋅ l o g 2 1 0.01 = 9.57 b i t s \frac{m}{n}=1.44\cdot log_2{\frac{1}{0.01}} = 9.57 bits nm=1.44⋅log20.011=9.57bits,哈希函数 k = l n 2 ⋅ m n = 0.7 ⋅ 9.57 = 6.7 b i t s k=ln2\cdot \frac{m}{n}=0.7\cdot9.57=6.7 bits k=ln2⋅nm=0.7⋅9.57=6.7bits;其中9.57是filter数组的空间,6.7是数组中被置一的空间;若要求误判率降低为原来的10%,则存储每个元素需要额外增加空间为: m 2 n 2 − m 1 n 1 = 1.44 ( l o g 2 10 P − l o g 2 1 p ) = 1.44 ⋅ l o g 2 10 = 4.78 b i t s \frac{m_2}{n_2}-\frac{m_1}{n_1} = 1.44(log_2{\frac{10}{P}}-log_2{\frac{1}{p}})=1.44\cdot log_2{10}=4.78bits n2m2−n1m1=1.44(log2P10−log2p1)=1.44⋅log210=4.78bits
-
Bloom Filter优缺点
-
优点
空间利用率很好,节省大量的存储空间
查询时间很好
-
缺点
存在一定概率的误判(False Positive)
不能删除已有元素(存在数组的一位被多次置一的情况,删除一元素将改变其他元素的存在性判断)
-
3.2.2 拓展CounterBloom Filter
为了解决Bloom Filter在删除元素存在问题。
因为删除元素,需要把该元素经过k次哈希函数对应数组的位置从1改写为0,为了避免数组中一个位置被多个元素写进1的信息被篡改,我们引入一个数组计数器;
在删除元素时,从计数器判断
if num>1: num--; else: bit==0;
同时受限于计数器的空间,计数器空间太小,同样会产生误判cache miss;Ref
3.2.3 拓展Compressed Bloom Filter
留一个坑,等会讨论
3.2.4 pybloom_live中BloomFilter的实现
from pybloom_live import BloomFilter
bf = BloomFilter(capacity,error_rate) #函数具体实现代码详见类的设计
3.3 Comparison
Each arriving key will be hashed H/K times to determine the corresponding locations
疑问:每一个key不是被计算H*K次吗?
Paper 1参考链接
使用Typora / Markdown中的链接 | typora中文网
Typora 使用 Markdown 嵌入 LaTeX 数学公式符号语法 - MuyiSir - 博客园 (cnblogs.com)
布隆过滤器BloomFilter举例说明+证明推导_小太阳~-CSDN博客_布隆过滤器推导
海量数据处理算法—Bloom Filter_黄规速博客:学如逆水行舟,不进则退-CSDN博客_bloom filter
据处理算法—Bloom Filter_黄规速博客:学如逆水行舟,不进则退-CSDN博客_bloom filter](https://blog.csdn.net/hguisu/article/details/7866173)