Bloom Filter

Bloom Filter是一種有趣的資料結構:支援以下操作:

1. Add:加入某個key到set中。
2. Query:檢查某個key是否在set中。

乍看之下沒什麼用,不過最大的特色在於他在Space跟Time的效率上非常好!缺點則是當加入太多key時,有機會產生false-positive(Query回傳true, 可是不在set中)的情況。

實際的作法是什麼呢?其實就是一個bit vector加上k個hash function。
每次當加入一個key的時候,就把該key對所有hash跑一遍,將各個function得到的結果都設為1

Query一樣跑過所有hash function, 然後檢查是不是所有位置的值都是1:

因此,為什麼有可能會產生false-positive的原因已經顯示出來了。當加入太多的key而導致bit vector幾乎都是1的時候,就有許多的key所hash出來的bit也剛好都被設成1了。

不過這個機率也是可以算出來的。如果bit vector的大小是m, hash function的個數是k,則false-positive的機率就是:

簡單的說,如果我們想要一個錯誤率1%的filter, 一個element只需要9.6個bit!如果還是太高,每個element只要增加4.8個bit, 錯誤率就會降低10倍!

至於這個資料結構有什麼用呢?
因為他可以很快的判別一個key存不存在,常見的用途像是spam filter, 或是檔cache前面做第一層的防線。最有名的大概是Google的Big Table了,bloom filter會擋在database query前面先濾掉不少的query。

Ruby中也有許多現成可用的實作了,像是這個

Reference:
http://en.wikipedia.org/wiki/Bloom_filter

http://www.igvita.com/2008/12/27/scalable-datasets-bloom-filters-in-ruby/

http://www.igvita.com/2010/01/06/flow-analysis-time-based-bloom-filters/

http://www.siaris.net/index.cgi/Programming/LanguageBits/Ruby/BloomFilter.rdoc

btw, Ilya Grigorik這人真的很神… 他的行文方式真是流暢。

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s