Bloom Filter改進(jìn)及其在分布式系統(tǒng)中的應(yīng)用研究.pdf

1、Bloom Filter采用一個(gè)位向量表示數(shù)據(jù)集合并且利用Hash函數(shù)有效支持查找。它能很好的解決一個(gè)問題：判定某個(gè)元素是否屬于給定集合。在分布式應(yīng)用環(huán)境中，Bloom Filter 在資源定位、路由查找等各方面都能夠得到很好的應(yīng)用。 近年來，針對(duì)Bloom Filter的基本原理存在多種改進(jìn)，其中主要包括計(jì)數(shù)型Bloom Filter、壓縮型Bloom Filter和拆分型Bloom Filter。計(jì)數(shù)型Bloom Filte

2、r能彌補(bǔ)平凡Bloom Filter的一個(gè)缺陷：只能往Bloom Filter中增加元素，而不能用于集合中元素的刪除；壓縮型Bloom Filter結(jié)合了數(shù)據(jù)壓縮理論，因而在分布式應(yīng)用中，能有效地降低網(wǎng)絡(luò)中Bloom Filter的數(shù)據(jù)傳輸量；而拆分型BloomFilter能較好地緩解分布式環(huán)境下集合元素動(dòng)態(tài)增長(zhǎng)的問題。 經(jīng)過對(duì)Bloom Filter及上述改進(jìn)的分析，本文提出兩種新型Bloom Filter：一種是K分組合型B

3、loom Filter，和拆分型Bloom Filter一樣，它針對(duì)的也是分布式環(huán)境下集合元素動(dòng)態(tài)增長(zhǎng)帶來的平凡Bloom Filter失效問題，本文主要把它與平凡Bloom Filter和拆分型Bloom Filter作比較并給出指標(biāo)分析，證明其能在誤稱率、向量空間和平均判定時(shí)間三個(gè)指標(biāo)中得到更好的平衡；第二種改進(jìn)型Bloom Filter是完全組合型Bloom Filter，它能完全消除平凡Bloom Filter引起的外部沖突，雖