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

1、資源交互共享是計算機網(wǎng)絡(luò)和分布式系統(tǒng)的核心，如何有效的表示信息和查詢信息是資源交互共享中最本質(zhì)的問題。高速發(fā)展的計算機網(wǎng)絡(luò)和計算機系統(tǒng)中，當數(shù)據(jù)不斷膨脹時，數(shù)據(jù)集合的表示和訪問越來越困難。因此，設(shè)計精簡數(shù)據(jù)結(jié)構(gòu)支持日益增長的數(shù)據(jù)存儲需求，設(shè)計與之對應(yīng)的算法支持海量數(shù)據(jù)下的高效查詢交互成為當前網(wǎng)絡(luò)、數(shù)據(jù)庫、分布式系統(tǒng)中資源交互共享的核心問題與嚴峻挑戰(zhàn)。 布魯姆過濾器(Bloom filter)采用一個位串表示數(shù)據(jù)集合并能有效支持元

2、素的哈希查找，是一種能夠簡潔的表示集合并支持集合查詢的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于數(shù)據(jù)庫、網(wǎng)絡(luò)和分布式系統(tǒng)中。本文從理論和應(yīng)用兩個方面對布魯姆過濾器查詢算法進行了深入的研究。系統(tǒng)地綜述了布魯姆過濾器查詢算法迄今為止的主要研究成果，分析了目前布魯姆過濾器查詢算法的研究現(xiàn)狀和缺陷，針對目前算法的不足，提出了分檔布魯姆過濾器查詢算法、可擴展布魯姆過濾器查詢算法、聯(lián)合多維布魯姆過濾器查詢算法、基于布魯姆過濾器距離的集合變動評估算法，并探討了布魯姆過濾器

3、代數(shù)運算和集合查詢的關(guān)系。研究布魯姆過濾器在分布式系統(tǒng)中的應(yīng)用，提出了基于布魯姆過濾器的節(jié)點軌跡標簽P2P副本一致性維護算法和基于布魯姆過濾器的混合移動自組織網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)模型。本文的創(chuàng)新性成果主要體現(xiàn)在以下幾個方面： 1)提出代價敏感的分檔布魯姆過濾器查詢算法針對現(xiàn)有的布魯姆過濾器查詢算法沒有考慮查詢失效代價這一缺陷，本文提出一種新的代價敏感的分檔布魯姆過濾器查詢算法。它將元素根據(jù)不同的查詢代價分為不同的子集，通過考查每檔子集最

4、低查詢失效率的關(guān)系，建立由每檔子集最低查詢失效率表示的集合最低查詢失效總代價目標函數(shù)，使用類目標函數(shù)梯度遺傳算法獲得每檔的最優(yōu)哈希函數(shù)個數(shù)k<,i>，完成集合到向量的映射與查找。仿真實驗結(jié)果表明，新的分檔布魯姆過濾器查詢算法和標準布魯姆過濾器算法相比，所用的查詢計算時間基本相同，而查詢失效總代價降低至少40％。 2)提出基于H<,3>哈希函數(shù)的可擴展布魯姆過濾器查詢算法布魯姆過濾器可擴展性主要是當集合元素動態(tài)增長超出過濾器算法設(shè)

5、計的容量時，如何調(diào)整布魯姆過濾器參數(shù)，使得布魯姆過濾器查詢算法有較低的查詢誤判率，同時具有可接受的計算性能，保證過濾器的可用性。本文研究布魯姆過濾器的可擴展性問題，提出基于H<,3>哈希函數(shù)的可擴展布魯姆過濾器查詢算法，當集合元素增長超過布魯姆過濾器集合容量限制時，通過增加成倍數(shù)擴大的布魯姆過濾器向量來保持很低的誤判率，利用H<,3>哈希函數(shù)實現(xiàn)可擴展布魯姆過濾器的設(shè)計以及過濾器中元素的插入、查詢過程。實驗分析表明，新的可擴展布魯姆過濾

6、器的元素查詢誤判率永遠小于動態(tài)布魯姆過濾器，平均為它的21.3％，且查詢時間呈對數(shù)增長，解決了現(xiàn)有算法查詢時間增長過快問題。 3)研究多維布魯姆過濾器查詢算法針對現(xiàn)有多維布魯姆過濾器查詢算法(MDBF)在多維元素表示和查詢時分割了各維屬性為一體的缺陷，提出一種改進的兩步表示和查詢的聯(lián)合多維布魯姆過濾器查詢算法(CMDBF)。CMDBF在MDBF的基礎(chǔ)上，增加一個聯(lián)合標準布魯姆過濾器CBF，將多維元素整體經(jīng)過兩次哈希運算表示到CB

7、F中。CMDBF的元素表示和查找分兩步進行，將MDBF作為元素表示和查找第一步，第二步聯(lián)合元素各屬性值利用CBF進行確認。仿真實驗表明，CMDBF相比MDBF查詢誤判率降低明顯。 4)探討布魯姆過濾器的代數(shù)運算布魯姆過濾器是集合到向量的一個映射，本文探討布魯姆過濾器的代數(shù)運算和集合查詢的關(guān)系。定義布魯姆過濾器的“并”，“交”，“異或”，“補”，“差”代數(shù)運算，從理論和仿真實驗兩方面分析布魯姆過濾器的代數(shù)運算和集合代數(shù)運算并集，交

8、集，異或集，補集，差集的元素查詢性質(zhì)。理論分析和實驗結(jié)果表明，布魯姆過濾器的“并”，“交”運算能夠支持集合并集交集的元素查詢，這一結(jié)論可以大大簡化利用布魯姆過濾器進行的系統(tǒng)設(shè)計。 5)提出基于布魯姆過濾器的節(jié)點軌跡標簽P2P副本一致性維護算法本文研究P2P系統(tǒng)副本一致性維護算法，從直接更改消息報文角度出發(fā)，提出一種基于布魯姆過濾器的節(jié)點軌跡標簽無結(jié)構(gòu)P2P副本一致性維護算法。通過在傳輸消息的報文中添加已接收更新消息的節(jié)點軌跡地址

9、鏈表標簽，可在消息傳輸源節(jié)點進行冗余判斷來減少冗余消息數(shù)目。因為直接存儲節(jié)點地址軌跡標簽算法的消息長度隨著消息傳輸輪數(shù)和網(wǎng)絡(luò)度數(shù)增加而不斷加大，論文采用布魯姆過濾器表示地址鏈表軌跡標簽。通過布魯姆過濾器這種簡潔的結(jié)構(gòu)表示地址鏈表，可以減少添加到報文中的軌跡長度，同時利用布魯姆過濾器的“并”運算還可以簡化傳輸節(jié)點的冗余判斷。仿真實驗表明：基于布魯姆過濾器的節(jié)點軌跡標簽算法可以大大降低冗余消息數(shù)目，提高P2P系統(tǒng)的可擴展性。副本節(jié)點網(wǎng)絡(luò)連通

10、性越強，消息數(shù)目和傳輸帶寬減少越明顯。 6)提出基于布魯姆過濾器的混合移動自組織網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)模型研究服務(wù)發(fā)現(xiàn)中服務(wù)信息的精簡存儲和查詢方法，提出基于布魯姆過濾器的混合移動自組織網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)模型。模型采用計數(shù)式布魯姆過濾器表示注冊服務(wù)目錄，采用兩層混合服務(wù)發(fā)現(xiàn)體系結(jié)構(gòu)和兩級服務(wù)信息存儲方式。論文詳細描述了基于布魯姆過濾器的服務(wù)發(fā)布、服務(wù)查詢、服務(wù)取消、服務(wù)注冊信息的擴散與同步和節(jié)點移動時對應(yīng)在服務(wù)協(xié)調(diào)者節(jié)點的相關(guān)操作和過程。定義布