亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Bloom Filter 原理與應(yīng)用

系統(tǒng) 1936 0

轉(zhuǎn)自: http://blog.huang-wei.com/2010/11/02/bloom-filter/

介紹

Bloom Filter是一種簡單的節(jié)省空間的隨機(jī)化的數(shù)據(jù)結(jié)構(gòu),支持用戶查詢的集合。一般我們使用STL的std::set, stdext::hash_set,std::set是用紅黑樹實(shí)現(xiàn)的,stdext::hash_set是用桶式哈希表。上述兩種數(shù)據(jù)結(jié)構(gòu),都會需要保存原始數(shù)據(jù)信息,當(dāng)數(shù)據(jù)量較大時(shí),內(nèi)存就會是個(gè)問題。如果應(yīng)用場景中允許出現(xiàn)一定幾率的誤判,且不需要逆向遍歷集合中的數(shù)據(jù)時(shí),Bloom Filter是很好的結(jié)構(gòu)。

優(yōu)點(diǎn)

  1. 查詢操作十分高效。
  2. 節(jié)省空間。
  3. 易于擴(kuò)展成并行。
  4. 集合計(jì)算方便。
  5. 代碼實(shí)現(xiàn)方便。
  6. 有誤判的概率,即存在False Position。
  7. 無法獲取集合中的元素?cái)?shù)據(jù)。
  8. 不支持刪除操作。

缺點(diǎn)

  1. 有誤判的概率,即存在False Position。
  2. 無法獲取集合中的元素?cái)?shù)據(jù)。
  3. 不支持刪除操作。

定義

Bloom Filter是一個(gè)有m位的位數(shù)組,初始全為0,并有k個(gè)各自獨(dú)立的哈希函數(shù)。

圖1

添加操作

每個(gè)元素,用k個(gè)哈希函數(shù)計(jì)算出大小為k的哈希向量
,將向量里的每個(gè)哈希值對應(yīng)的位設(shè)置為1。時(shí)間復(fù)雜度為 ,一般字符串哈希函數(shù)的時(shí)間復(fù)雜度也就是

查詢操作

和添加類似,先計(jì)算出哈希向量,如果每個(gè)哈希值對應(yīng)的位都為1,則該元素存在。時(shí)間復(fù)雜度與添加操作相同。

示例

圖2表示m=16,k=2的Bloom Filter, 和 的哈希值分別為(3, 6)和(10, 3)。

圖2

False Position

如果某元素不在Bloom Filter中,但是它所有哈希值的位置均被設(shè)為1。這種情況就是False Position,也就是誤判。

借用示例,如下:

圖3

這個(gè)問題其實(shí)和哈希表中的沖突是相同的道理,哈希表中可以使用開散列和閉散列的方法,而Bloom Filter則允許這樣的情況發(fā)生,它更關(guān)心于誤判的發(fā)生概率。

概率

宏觀上,我們能得出以下結(jié)論:

參數(shù)表 變量 減少 增加
哈希函數(shù)總數(shù) K l 更少的哈希值計(jì)算

l 增加False Position的概率

l 更多的計(jì)算

l 位值0減少

Bloom Filter 大小 M l 更少的內(nèi)存

l 增加False Position的概率

l 更多的內(nèi)存

l 降低概率

元素總數(shù) N l 降低False Position的概率 l 增加概率

False Position的概率為

假設(shè)m和n已知,為了最小化False Position,則

數(shù)據(jù)

圖4

擴(kuò)展

Counter Bloom Filter

Bloom Filter有個(gè)缺點(diǎn),就是不支持刪除操作,因?yàn)樗恢滥骋粋€(gè)位從屬于哪些向量。那我們可以給Bloom Filter加上計(jì)數(shù)器,添加時(shí)增加計(jì)數(shù)器,刪除時(shí)減少計(jì)數(shù)器。

但這樣的Filter需要考慮附加的計(jì)數(shù)器大小,假如同個(gè)元素多次插入的話,計(jì)數(shù)器位數(shù)較少的情況下,就會出現(xiàn)溢出問題。如果對計(jì)數(shù)器設(shè)置上限值的話,會導(dǎo)致Cache Miss,但對某些應(yīng)用來說,這并不是什么問題,如Web Sharing。

Compressed Bloom Filter

為了能在服務(wù)器之間更快地通過網(wǎng)絡(luò)傳輸Bloom Filter,我們有方法能在已完成Bloom Filter之后,得到一些實(shí)際參數(shù)的情況下進(jìn)行壓縮。

將元素全部添加入Bloom Filter后,我們能得到真實(shí)的空間使用率,用這個(gè)值代入公式計(jì)算出一個(gè)比m小的值,重新構(gòu)造Bloom Filter,對原先的哈希值進(jìn)行求余處理,在誤判率不變的情況下,使得其內(nèi)存大小更合適。

應(yīng)用

加速查詢

適用于一些key-value存儲系統(tǒng),當(dāng)values存在硬盤時(shí),查詢就是件費(fèi)時(shí)的事。

將Storage的數(shù)據(jù)都插入Filter,在Filter中查詢都不存在時(shí),那就不需要去Storage查詢了。

當(dāng)False Position出現(xiàn)時(shí),只是會導(dǎo)致一次多余的Storage查詢。

圖5

l Google的BigTable也使用了Bloom Filter,以減少不存在的行或列在磁盤上的查詢,大大提高了數(shù)據(jù)庫的查詢操作的性能。

l 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存儲URLs,除了高效的查詢外,還能很方便得傳輸交換Cache信息。

網(wǎng)絡(luò)應(yīng)用

l P2P網(wǎng)絡(luò)中查找資源操作,可以對每條網(wǎng)絡(luò)通路保存Bloom Filter,當(dāng)命中時(shí),則選擇該通路訪問。

l 廣播消息時(shí),可以檢測某個(gè)IP是否已發(fā)包。

l 檢測廣播消息包的環(huán)路,將Bloom Filter保存在包里,每個(gè)節(jié)點(diǎn)將自己添加入Bloom Filter。

l 信息隊(duì)列管理,使用Counter Bloom Filter管理信息流量。

垃圾郵件地址過濾

來自于Google黑板報(bào)的例子。

像網(wǎng)易,QQ這樣的公眾電子郵件(email)提供商,總是需要過濾來自發(fā)送垃圾郵件的人(spamer)的垃圾郵件。

一個(gè)辦法就是記錄下那些發(fā)垃圾郵件的 email 地址。由于那些發(fā)送者不停地在注冊新的地址,全世界少說也有幾十億個(gè)發(fā)垃圾郵件的地址,將他們都存起來則需要大量的網(wǎng)絡(luò)服務(wù)器。

如果用哈希表,每存儲一億個(gè) email 地址,就需要 1.6GB 的內(nèi)存(用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè) email 地址對應(yīng)成一個(gè)八字節(jié)的信息指紋,然后將這些信息指紋存入哈希表,由于哈希表的存儲效率一般只有 50%,因此一個(gè) email 地址需要占用十六個(gè)字節(jié)。一億個(gè)地址大約要 1.6GB, 即十六億字節(jié)的內(nèi)存)。因此存貯幾十億個(gè)郵件地址可能需要上百 GB 的內(nèi)存。

而Bloom Filter只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題。

Bloom Filter決不會漏掉任何一個(gè)在黑名單中的可疑地址。而至于誤判問題,常見的補(bǔ)救辦法是在建立一個(gè)小的白名單,存儲那些可能別誤判的郵件地址。

引用

[1] Bloom filter; http://en.wikipedia.org/wiki/Bloom_filter

[2] Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol; http://pages.cs.wisc.edu/~cao/papers/summary-cache/

[3] Network Applications of Bloom Filters: A Survey; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.9672&rep=rep1&type=pdf

[4] An Examination of Bloom Filters and their Applications; http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf

[5] 數(shù)學(xué)之美系列二十一 - 布隆過濾器(Bloom Filter); http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html

Bloom Filter 原理與應(yīng)用


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久精品久久久久久久久人 | 另类 欧美 视频二区 | 亚洲欧美日韩国产精品26u | 国产69精品久久久久999小说 | 国产激情久久久久久影院 | 亲热网站| 在线中文字幕亚洲 | 毛片不卡一区二区三区 | 日本伊人精品一区二区三区 | 亚洲综合色就色手机在线观看 | 久草在线在线视频 | 久久99精品国产麻豆 | 欧美日韩亚洲视频 | 曰本性l交片视频视频 | 亚洲欧美综合乱码精品成人网 | 青草青在线免费视频 | 四虎在线观看网址 | 91国语精品自产拍在线观看一 | 亚洲va久久久噜噜噜久久男同 | 欧美成人精品在线 | 欧美日本综合一区二区三区 | 91精品国产欧美一区二区 | 久久久久久88色愉愉 | 99视频在线免费观看 | 成人国产三级在线播放 | 日韩五月天 | 91视频第一页 | 奇米影视7777777 | 欧美三级a| 一区二区三区四区产品乱码伦 | 国产午夜亚洲精品国产 | 国产丰满老厨女房乱 | 日韩 欧美 中文 | 欧美激情在线播放一区二区 | 91亚洲影院 | 日本爱爱视频 | 欧美日本一二三区 | 四虎影院精品在线观看 | 亚洲国产精品日韩在线观看 | 亚洲九九九 | 欧洲成人全免费视频网站 |