多布魯姆過濾器查詢算法及其應(yīng)用研究.pdf

1、布魯姆過濾器是一種表示集合的空間高效的有損數(shù)據(jù)結(jié)構(gòu)，支持快速的數(shù)據(jù)成員查詢，能有效地過濾不屬于集合的成員。布魯姆過濾器被廣泛應(yīng)用于數(shù)據(jù)庫、網(wǎng)絡(luò)和分布式系統(tǒng)，它在需要共享現(xiàn)有數(shù)據(jù)信息的分布式應(yīng)用系統(tǒng)中有巨大的應(yīng)用潛力。針對布魯姆過濾器算法和應(yīng)用的研究已被越來越多的研究團體所重視，涌現(xiàn)出了大量布魯姆過濾器算法的變種及相關(guān)應(yīng)用的研究論文，而且這種快速發(fā)展的勢頭還將持續(xù)下去，必定會出現(xiàn)更多布魯姆過濾器算法的相關(guān)變種及應(yīng)用研究。
　　 通

2、常我們使用布魯姆過濾器的一般場景是:將集合S表示到布魯姆過濾器這一精簡結(jié)構(gòu)中，在需要查詢元素是否屬于集合S時，使用布魯姆過濾器而不是集合S本身進行集合成員查詢，節(jié)約存儲空間及提高查詢的時間效率。目前大多數(shù)有關(guān)布魯姆過濾器的擴展算法及應(yīng)用研究主要是針對單個布魯姆過濾器結(jié)構(gòu)進行的。本文的研究工作則是考察如何使用多個布魯姆過濾器結(jié)構(gòu)進行相關(guān)查詢，并將之用于分布式內(nèi)容分發(fā)系統(tǒng)、數(shù)據(jù)同步系統(tǒng)等。
　　 本文對多布魯姆過濾器查詢算法從理論分

3、析和實際應(yīng)用兩個方面進行了深入的研究。首先分析網(wǎng)絡(luò)高速發(fā)展給多布魯姆過濾器查詢算法帶來的機遇，指出多布魯姆過濾器查詢算法研究的重要意義。然后，概括了多布魯姆過濾器查詢算法的研究現(xiàn)狀和多布魯姆過濾器查詢算法目前的主要研究成果?？紤]到單布魯姆過濾器查詢算法在解決分布式數(shù)據(jù)分發(fā)及數(shù)據(jù)同步等問題時不能完全勝任，本文提出了使用多個布魯姆過濾器結(jié)構(gòu)進行查詢的數(shù)個多布魯姆過濾器查詢算法，如雙布魯姆過濾器直接查詢算法、計數(shù)布魯姆過濾器代數(shù)運算查詢算法、

4、使用多個標準布魯姆過濾器進行查詢的數(shù)據(jù)調(diào)和算法及使用多計數(shù)布魯姆過濾器運算的數(shù)據(jù)調(diào)和算法。本文的創(chuàng)新性成果主要體現(xiàn)在以下幾個方面:
　　 1)探討雙布魯姆過濾器直接查詢法的查詢性能
　　 探討直接使用兩個集合的布魯姆過濾器結(jié)構(gòu)查詢集合并集、交集、補集、差集或?qū)ΨQ差成員的性能問題，即雙布魯姆過濾器直接查詢法的性能。理論分析和實驗結(jié)果表明，雙布魯姆過濾器直接查詢法能夠較好地支持集合并集、交集、補集、差集及對稱差的成員查詢問題

5、，其中使用雙布魯姆過濾器直接查詢法進行并集查詢及交集查詢不會產(chǎn)生假陰性，僅有少量假陽性的存在，而雙布魯姆過濾器直接查詢法查詢補集、差集及對稱差則除存在少量假陽性外，還存在少量假陰性，即部分本來屬于補集、差集或?qū)ΨQ差的元素被判為不屬于補集、差集或?qū)ΨQ差。
　　 2)研究多個計數(shù)布魯姆過濾器向量進行代數(shù)運算(簡稱為計數(shù)布魯姆過濾器代數(shù)運算)的性質(zhì)
　　 由于在使用雙布魯姆過濾器直接查詢法查詢補集、差集及對稱差元素時，存在假陰

6、性問題，因此，我們嘗試從計數(shù)布魯姆過濾器向量運算的角度尋求能解決前述假陰性問題的方法，探討兩個或多個計數(shù)布魯姆過濾器的代數(shù)運算和集合運算的一致性關(guān)系，研究使用計數(shù)布魯姆過濾器代數(shù)運算進行集合成員查詢的性能。理論分析和實驗結(jié)果表明，計數(shù)布魯姆過濾器的并、交、補、減、異或運算產(chǎn)生的新過濾器依然保持計數(shù)布魯姆過濾器的特征，支持元素的刪除操作，不會出現(xiàn)假陰性，能用于集合并集、交集、補集、差集及對稱差的成員查詢;與雙布魯姆過濾器直接查詢法相比，使

7、用計數(shù)布魯姆過濾器代數(shù)運算后的過濾器進行補集、差集及對稱差成員查詢，不存在前述假陰性問題，空間效率能提高一倍，時間效率亦能顯著地得到改善。計數(shù)布魯姆過濾器代數(shù)運算的使用有利于進一步擴展計數(shù)布魯姆過濾器的應(yīng)用范圍。
　　 3)提出基于多標準布魯姆過濾器運算的精確集合調(diào)和方法
　　 分布式系統(tǒng)中，集合調(diào)和是指分布式節(jié)點交換各自節(jié)點的數(shù)據(jù)集合本身或數(shù)據(jù)集合的某種表示，找出集合的差集元素，進而獲得數(shù)據(jù)集合并集的過程，在這一過程中

8、，節(jié)點間花費的通信代價(節(jié)點間的消息交換輪數(shù)及傳輸消息位數(shù))越少越好。集合調(diào)和問題對于分布式文件分發(fā)、閑談協(xié)議、同步與復制協(xié)議等分布式計算應(yīng)用來說，是一個重要的基礎(chǔ)構(gòu)件。本文在分析現(xiàn)有特征多項式插值精確集合調(diào)和法的工作原理的基礎(chǔ)上，提出了一種基于多標準布魯姆過濾器運算的精確集合調(diào)和方法(BFESR)。使用特征多項式插值調(diào)和法(Characteristic polynomialinterpolation-based synchroniza

9、tion，CPISync)時有一個前提:插值時的求值點數(shù)要大于對稱差規(guī)模(即|SA-SB|+|SB-SA|)。分布式系統(tǒng)中，對稱差規(guī)模的上界值往往無法事先獲知，從而不能簡單地調(diào)用CPISync算法完成調(diào)和?，F(xiàn)有的解決方法通常是使用試探法，即逐次增加求值點數(shù)和特征多項式值個數(shù)，直至求值點總數(shù)超過對稱差規(guī)模，才能成功插值，實現(xiàn)集合調(diào)和。BFESR首先使用兩個布魯姆過濾器的內(nèi)積運算或本文提出的準交集查詢法估算出對稱差規(guī)模;然后以逐輪增加的求值

10、點和特征多項式值作為插值算法的輸入，重復調(diào)用插值算法，直至確認成功;最后進行因式分解得到差集元素，進而獲取并集完成調(diào)和。通常，BFESR調(diào)和過程中，調(diào)用一次插值算法即能成功。理論分析和實驗結(jié)果表明，使用布魯姆過濾器內(nèi)積運算和準交集查詢法估算對稱差規(guī)模，其準確程度均較高，而且準交集查詢法得到的估算值更為接近實際對稱差規(guī)模。與已有的試探法進行比較，BFESR調(diào)和時間和消息交換輪數(shù)降低非常明顯，尤其是使用準交集查詢法估算對稱差規(guī)模的BFESR

11、方法，其調(diào)和效率更高。
　　 4)提出基于多計數(shù)布魯姆過濾器運算的精確集合調(diào)和方法
　　 由于BFESR算法中使用的標準布魯姆過濾器不支持集合元素的動態(tài)更新，若用于更新頻繁的P2P網(wǎng)絡(luò)等分布式系統(tǒng)則需要定時重建標準布魯姆過濾器，這樣會增加系統(tǒng)實現(xiàn)的負擔及難度，因此，為解決BFESR調(diào)和算法的這一應(yīng)用局限性，本文提出了一種基于多計數(shù)布魯姆過濾器運算的精確集合調(diào)和方法(CBFESR)，該方法將集合用計數(shù)布魯姆過濾器表示，利用