不需要存储key
Tagged Tags:

Bloomier filters

Chazelle
等人建议了二个通用的布隆过滤器,该布隆过滤器能够将某一值与种种已经插入的要素关联起来,并贯彻了贰个提到数组Map[10]。与常见的布隆过滤器一样,Chazelle完成的布隆过滤器也能够达成异常的低的空间消耗,但与此同一时候也会发出false
positive,然则,在Bloomier filter中,某 key
若是不在 map 中,false positive在会回来时会被定义出的。该Map
结构不会回去与 key 相关的在 map 中的错误的值。

Compact approximators[11]

False positives 可能率推导

假设 Hash 函数以等概率条件选取并设置 Bit Array
中的某人,m 是该位数组的高低,k 是 Hash
函数的个数,那么位数组中某一一定的位在实行元素插入时的 Hash
操作中从不被置位的可能率是:

图片 1

那么在颇具 k 次 Hash 操作后该位都未曾被置 “1” 的可能率是:

图片 2

一经大家插入了 n 个因素,那么某一人依旧为 “0” 的票房价值是:

图片 3

故而该位为 “1”的概率是:

图片 4

于今检验某一因素是或不是在该集合中。注脚有个别成分是还是不是在集合中所需的 k
个职位都遵从如上的方法设置为
“1”,然而该措施可能会使算法错误的感到某一原先不在集结中的成分却被检查测量试验为在该集结中(False
Positives),该可能率由以下公式明确:

图片 5

实际上述结果是在假定由种种 Hash 计算出要求安装的位(bit)
的职位是互相独立为前提计算出来的,轻易看出,随着 m
(位数组大小)的加码,假正例(False
Positives)的概率会稳中有降,同有的时候间随着插入成分个数 n 的增添,False
Positives的票房价值又会稳中有升,对于给定的m,n,如何挑选Hash函数个数 k
由以下公式明确:

图片 6

此时False Positives的票房价值为:

图片 7

而对于给定的False Positives可能率 p,如何抉择最优的位数组大小 m 呢,

图片 8

上式评释,位数组的大小最佳与插入成分的个数成线性关系,对于给定的
m,n,k,假正例可能率最大为:

图片 9

 

布隆过滤器相关扩充

连锁链接

  • Table of false-positive rates for different
    configurations from
    a University of
    Wisconsin–Madison website
  • Interactive Processing
    demonstration from
    ashcan.org
  • “More Optimal Bloom Filters,” Ely Porat (Nov/2007) Google TechTalk
    video on YouTube
  • “Using Bloom
    Filters” Detailed
    Bloom Filter explanation
    using Perl

可取:不供给仓库储存key,节省空间

  1. 先是须要k个hash函数,每一种函数能够把key散列成为1个整数
  2. 开始化时,要求二个长短为n比特的数组,每一个比特位起先化为0
    3.
    某部key加入会集时,用k个hash函数总括出k个散列值,并把数组中对应的比特地方为1
    4.
    决断有些key是或不是在汇聚时,用k个hash函数总结出k个散列值,并询问数组中对应的比特位,假使具备的比特位都以1,感觉在会集中。

布隆过滤器[1](Bloom Filter)是由布隆(BurtonHowardBloom)在一九七〇年提议的。它实际上是由二个不短的二进制向量和一密密麻麻随机映射函数组成,布隆过滤器能够用来检索贰个成分是或不是在三个凑合中。它的独到之处是空中成效和查询时间都远远当先一般的算法,劣点是有早晚的误识别率(假正例False
positives,即Bloom
Filter报告某一因素存在于某集结中,可是其实该因素并不在集合中)和删除困难,不过从未识别错误的情状(即假反例False
negatives,假使某些成分确实未有在该会集中,那么Bloom Filter
是不会告知该因素存在于聚集中的,所以不会漏报)。

缺点:

Attenuated Bloom filters[14]

那是一旦增添叁个bloom算法的劳务,后端插入二个key时,在那个服务中安装叁次
需求查询后端时,先推断key在后端是不是留存,那样就会幸免后端的下压力。

 

下图是布隆过滤器假正例可能率 p 与位数组大小 m 和集合中插入成分个数 n
的关联图,假定 Hash
函数个数选用最优数目:图片 10

不需要存储key。 

图片 11

Stable Bloom filters[12]

独立的使用场景:
不需要存储key。一点存款和储蓄系统的布置中,会存在空查询破绽:当查问贰个不设有的key时,须要拜谒慢设备,导致功效低下。
例如多少个前端页面包车型客车缓存系统,大概这么设计:先查询某些页面在本土是或不是存在,假若存在就向来回到,假设不设有,就从后端获取。然而当频仍从缓存系统查询一个页面时,缓存系统将会频繁呼吁后端,把压力导入后端。

  1. 算法推断key在联谊中时,有必然的可能率key其实不在群集中
  2. 力不从心删除

图片 12

算法:

 Counting filters

中央的布隆过滤器不帮衬删除(Deletion)操作,但是Counting filters
提供了一种能够不要再行营造布隆过滤器但却帮忙成分删除操作的不二等秘书技。在Counting
filters中本来的位数组中的每一人由 bit 扩张为 n-bit
计数器,实际上,基本的布隆过滤器可以看做是只有一个人的计数器的Counting
filters。原本的插入操作也被扩充为把 n-bit
的位计数器加1,查找操作即检查位数组非零就能够,而删除操作定义为把位数组的照料位减1,但是该办法也可以有位的算术溢出标题,即某个人在频仍刨除操作后可能变为负值,所以位数组大小
m 要求充足大。其他叁个主题材料是Counting
filters不辜负有伸缩性,由于Counting
filters无法扩展,所以必要保留的最大的成分个数必要提前领略。不然即使插入的因素个数超越了位数组的容积,false
positive的发生可能率将会大幅度增加。当然也会有人提议了一种基于 D-left Hash
方法完结协理删除操作的布隆过滤器,相同的时候空间成效也比Counting filters高。

不需要存储key。优点

相比较之下于任何的数据结构,布隆过滤器在上空和时间方面都有远大的优势。布隆过滤器存款和储蓄空间和插入/查询时间都以常数。其它,
Hash
函数相互之间未有提到,方便由硬件并行完毕。布隆过滤器无需仓库储存成分自身,在好几对保密须要十二分严俊的场地有优势。

布隆过滤器能够表示全集,其余任何数据结构都无法;

k 和 m 同样,使用一样组 Hash
函数的多少个布隆过滤器的交并差运算能够运用位操作进行。

 

基本概念

假使想看清叁个成分是否在一个集聚里,一般想到的是将具有因素保存起来,然后经过相比明确。链表,树等等数据结构都以这种思路.
不过随着会集桐月素的增添,大家须求的存放空间尤其大,检索速度也更为慢。可是世界上还应该有一种叫作散列表(又叫哈希表,Hash
table)的数据结构。它能够由此三个Hash函数将三个因素映射成三个位阵列(Bit
Array)中的多个点。那样一来,大家只要看看这几个点是还是不是 1
就掌握能够凑合中有未有它了。那正是布隆过滤器的着力思想。

Hash面对的标题就是争持。假诺 Hash 函数是优良的,要是大家的位阵列长度为 m
个点,那么只要大家想将顶牛率裁减到比如 1%, 那么些散列表就只好容纳 m/100
个成分。显著那就不叫空间有效了(Space-efficient)。化解措施也轻巧,正是应用八个Hash,如若它们有七个说成分不在会集中,这必将就不在。若是它们都说在,固然也许有一定也许它们在撒谎,但是直觉上判定这种业务的概率是相当低的。

 

 

Scalable Bloom filters[13]

在通常生活中,满含在安排计算机软件时,大家平常要认清一个因素是或不是在贰个会晤中。比方在字管理软件中,需求检查一个匈牙利(Magyarország)语单词是不是拼写正确(也等于要看清
它是还是不是在已知的字典中);在
FBI,叁个疑凶的名字是还是不是早就在疑忌名单上;在网络爬虫里,贰个网站是或不是被访谈过等等。最直白的法子正是将集结中全体的要素存在Computer中,境遇三个新
元素时,将它和集纳中的成分直接比较就能够。一般来说,Computer中的集结是用哈希表(hash
table)来囤积的。它的补益是高速正确,瑕玷是费存储空间。当集结比非常的小时,那一个主题素材不刚强,可是当集结巨大时,哈希表存款和储蓄效能低的标题就显现出来
了。比方说,三个象 Yahoo,Hotmail 和 Gmai
那样的众生电子邮件(email)提供商,总是供给过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。三个办法正是记录下那八个发垃圾邮件的
email
地址。由于那么些发送者不停地在注册新的地点,整个世界少说也是有几十亿个发垃圾邮件的地址,将他们都存起来则供给大批量的互联网服务器。借使用哈希表,每存款和储蓄一亿
个 email 地址, 就供给 1.6GB 的内部存款和储蓄器(用哈希表达成的具体办法是将每贰个email
地址对应成贰个八字节的消息指纹(详见:googlechinablog.com/2006/08/blog-post.html),
然后将这个音信指纹存入哈希表,由于哈希表的积存功能一般唯有 四分之二,由此叁个email 地址供给占用拾柒个字节。一亿个地点大概要 1.6GB,
即十六亿字节的内部存款和储蓄器)。因而存贮几十亿个邮件地址也许须要广大 GB
的内部存款和储蓄器。除非是一流Computer,一般服务器是力不能够及积累的[2]。(该段援引Google数学之美:

直观的说,bloom算法类似三个hash
set,用来决断有个别成分(key)是或不是在某个群集中。
和一般的hash
set差别的是,那几个算法没有需求存放key的值,对于各类key,只需求k个比特位,每种存款和储蓄二个标记,用来剖断key是或不是在会集中。

缺点

不过布隆过滤器的症结和优点同样醒目。误算率(False
Positive)是在那之中之一。随着存入的要素数量净增,误算率随之大增。可是一旦成分数量太少,则应用散列表足矣。

别的,一般情况下不能够从布隆过滤器中剔除成分.
大家很轻松想到把位列阵形成整数数组,每插入多个因素相应的计数器加1,
那样删除元素时将计数器减掉就可以了。可是要保障安全的删减成分其实不然轻便。首先咱们不可能不保险删除的因素的确在布隆过滤器里面.
那一点单凭这一个过滤器是力不从心担保的。别的计数器回绕也会招致问题。

Data synchronization

Byers等人提议了使用布隆过滤器近似数据同步[9]。

参照他事他说加以考察资料

[1]维基百科:布隆过滤器:

[2]数学之美二十一:布隆过滤器(Bloom
Filter):

[3]Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh,
Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew
et al. (2006), “Bigtable: A Distributed Storage System for Structured
Data”, 不需要存储key。Seventh
Symposium on Operating System Design and Implementation

[4]Wessels, Duane (January 2004), “10.7
Cache Digests”, Squid: The Definitive Guide (1st ed.), O’Reilly Media,
p. 172, ISBN 0-596-00162-2,
“Cache Digests are based on a technique first published by Pei Cao,
called Summary Cache. The fundamental idea is to use a Bloom filter to
represent the cache contents.”

[5]

[6]

[7]

[8]

[9]Byers,
John W.; Considine, Jeffrey; Mitzenmacher, Michael; Rost, Stanislav
(2004), “Informed content delivery across adaptive overlay
networks”, IEEE/ACM Transactions on Networking 12 (5): 767,
DOI:10.1109/TNET.2004.836103

[10]Chazelle,
Bernard; Kilian, Joe; Rubinfeld, Ronitt; Tal, Ayellet (2004), “The Bloomier filter: an efficient data structure
for static support lookup tables”, Proceedings of the Fifteenth Annual
ACM-SIAM Symposium on Discrete Algorithms
, pp. 30–39

[11]Boldi, Paolo; Vigna, Sebastiano (2005), “Mutable
strings in Java: design, implementation and lightweight text-search
algorithms”, Science of Computer Programming 54 (1): 3–23,
DOI:10.1016/j.scico.2004.05.003

[12]Deng, Fan; Rafiei, Davood (2006), “Approximately Detecting Duplicates for Streaming
Data using Stable Bloom Filters”, Proceedings of the ACM SIGMOD
Conference
, pp. 25–36

[13]Almeida, Paulo; Baquero, Carlos; Preguica, Nuno;
Hutchison, David (2007), “Scalable Bloom
Filters”, Information Processing Letters 101 (6): 255–261,
DOI:10.1016/j.ipl.2006.10.007

[14]

 

Bloom Filter 用例

Google 盛名的布满式数据库 Bigtable
使用了布隆过滤器来搜索不设有的行或列,以压缩磁盘查找的IO次数[3]。

Squid 网页代理缓存服务器在 cache
digests 中选择了也布隆过滤器[4]。

Venti 文档存款和储蓄系统也运用布隆过滤器来检查评定先前储存的数量[5]。

SPIN 模型检验器也利用布隆过滤器在大范围验证难点时追踪可达状态空间[6]。

谷歌 Chrome浏览器选拔了布隆过滤器加快安全浏览服务[7]。

在非常多Key-Value系统中也使用了布隆过滤器来加速查询进程,如
Hbase,Accumulo,Leveldb,一般来说,Value
保存在磁盘中,访问磁盘须要费用大量时间,可是使用布隆过滤器能够快捷推断某些Key对应的Value是或不是存在,因而得防止止过多不须求的磁盘IO操作,只是引进布隆过滤器会推动一定的内部存储器消耗,下图是在Key-Value系统中布隆过滤器的标准使用:

图片 13

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注