Sketch之初见BF

目录

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} M1​k∗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​(ai​x+bi​) mod r mod M

Sketch之初见BF

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,也不代表该元素在该集合中

Sketch之初见BF

3.2.1 Bloom Filter的分析

  1. 一个bloom filter的参数误判率推导

    参数 参数说明
    m bit数组的宽度(bit数)
    n 插入其中key的数量
    k 使用hash函数的个数
    f False Positive的概率
  2. 错误率的推导

    某一位在插入新元素时,没有被置一的概率: 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增大时,误判率增大。

  3. 最佳哈希函数 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) …

  4. 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⋅log2​0.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 n2​m2​​−n1​m1​​=1.44(log2​P10​−log2​p1​)=1.44⋅log2​10=4.78bits

  5. Bloom Filter优缺点

    1. 优点

      空间利用率很好,节省大量的存储空间

      查询时间很好

    2. 缺点

      存在一定概率的误判(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 - 知乎 (zhihu.com)

据处理算法—Bloom Filter_黄规速博客:学如逆水行舟,不进则退-CSDN博客_bloom filter](https://blog.csdn.net/hguisu/article/details/7866173)

Bloom Filter - 知乎 (zhihu.com)

上一篇:8.过滤器Filter


下一篇:hutool+poi库+excel导出功能