基于樹(shù)形結(jié)構(gòu)的布魯姆過(guò)濾器研究.pdf

1、布魯姆過(guò)濾器算法憑借其簡(jiǎn)單迅捷的查詢方式和優(yōu)異的空間效率而受到了廣泛關(guān)注,但是布魯姆過(guò)濾器算法并不能支持?jǐn)?shù)據(jù)集成員的動(dòng)態(tài)更新尤其是不能支持?jǐn)?shù)據(jù)集成員的刪除操作,因?yàn)閯h除操作會(huì)引起布魯姆過(guò)濾器的誤判,從而影響查詢的準(zhǔn)確性即降低查詢的精度;計(jì)數(shù)式布魯姆過(guò)濾器算法使用Coutner計(jì)數(shù)器替代布魯姆過(guò)濾器中的比特位,因此能夠很好地支持?jǐn)?shù)據(jù)集成員的動(dòng)態(tài)更新,但是使用計(jì)數(shù)器也存在著空間開(kāi)銷過(guò)大的問(wèn)題。關(guān)于布魯姆過(guò)濾器算法的各種研究針對(duì)布魯姆過(guò)濾器在

2、空間開(kāi)銷、時(shí)間開(kāi)銷、查詢精度三個(gè)方面的效率提出了多種行之有效的改進(jìn)方案。
　　 本文針對(duì)以上三種性能指標(biāo),提出了一種基于多層次結(jié)構(gòu)的樹(shù)形布魯姆過(guò)濾器(Tree-based Bloom Filter簡(jiǎn)稱TBF)。多層次結(jié)構(gòu)的TBF算法是基于BloomingTree算法在空間開(kāi)銷上的優(yōu)勢(shì),并針對(duì)其所存在的缺陷設(shè)計(jì)的一種更加快速高效的算法。TBF查詢、更新方法是從尋找更有效的方法,來(lái)替代原來(lái)BloomingTree算法中容易導(dǎo)致錯(cuò)誤的

3、邏輯索引方式,并減少原方法在每一層都必須進(jìn)行的比特位查詢確認(rèn)操作這兩個(gè)方面來(lái)進(jìn)行考慮,改進(jìn)與設(shè)計(jì)了TBF算法的查詢索引方式和與之相應(yīng)的更新算法。通過(guò)新的更加快速高效的查詢索引方式,能夠迅速、有效的查找到應(yīng)該執(zhí)行查詢、更新的相應(yīng)位置或相應(yīng)比特位,從而完成對(duì)數(shù)據(jù)集中數(shù)據(jù)成員的查詢匹配,或是對(duì)數(shù)據(jù)集成員的更新工作;而TBF查詢算法通過(guò)減少比特位確認(rèn)操作,提高了TBF查詢和更新的速度,節(jié)省了時(shí)間開(kāi)銷。TBF算法能夠在低于計(jì)數(shù)式布魯姆過(guò)濾器的空間

4、需求的條件下實(shí)現(xiàn)與計(jì)數(shù)式布魯姆過(guò)濾器相同的功能,而且TBF算法比之BloomingTree算法更加快速高效。經(jīng)過(guò)實(shí)驗(yàn)證明:與BloomingTree算法相比,TBF算法能夠有效的解決BloomingTree算法在邏輯索引時(shí)所存在的錯(cuò)誤查詢問(wèn)題,而且比BloomingTree算法時(shí)間上更加高效:在層數(shù)不變假陽(yáng)性相同條件下,查詢時(shí)間平均提高13.4％;在假陽(yáng)性不變層數(shù)相同條件下,插入時(shí)間平均提高17.9％,刪除時(shí)間平均提高12％。因此,TB