[發明專利]一種可擴展的布魯姆過濾器查詢方法及其元素插入方法

無效

• 申請號: 200710035385.5
• 申請日: 2007-07-18
• 公開（公告）號: CN101082923A
• 公開（公告）日: 2007-12-05
• 發明（設計）人: 謝鯤;閔應驊;張大方;文吉剛;謝高崗
• 申請（專利權）人: 湖南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 長沙正奇專利事務所有限責任公司
• 代理人: 馬強

技術領域

本發明是涉及分布式計算技術領域，特別是涉及分布式系統產生大量數據、需要進行交互查詢的應用，具體是一種可擴展布魯姆過濾器查詢方法及其元素插入方法。

背景技術

隨著計算技術和因特網的高速發展，數據量不斷加大，網絡的異構性和復雜性不斷增加，日趨多樣化和復雜化的計算機環境，需要在形式、規模、功能和性能等多個層次展開計算系統的可擴展性研究。存儲系統的可擴展性是當前計算機研究的熱點。布魯姆過濾器對數據集合采用一個位串表示并能有效支持元素的哈希查找，是一種能夠表示集合、支持集合查詢的簡潔數據結構。面對不斷發展的計算機和網絡環境，數據膨脹時，研究可擴展的布魯姆過濾結構支持動態集合查詢成為布魯姆過濾器在分布式系統應用中迫切需要解決的問題。

布魯姆過濾器(Bloom?Filter)對數據集合采用一個位串表示并能有效支持集合元素的哈希查找，是一種能夠表示集合、支持集合查詢的簡潔數據結構，它能夠有效的過濾掉不屬于集合的元素，因其是由B.Bloom提出的而稱為布魯姆過濾器(Bloom?Filter)。由于其哈希查找的常數時間和存儲空間開銷較小，從而使它具有很好的實用價值。

布魯姆過濾器自1970年提出以來，被廣泛應用到各種計算機系統中，以提高龐大數據集的查找效率。早期的應用主要集中在數據庫操作和字典查詢操作。最近，隨著網絡研究的發展以及新的覆蓋網和P2P網絡應用技術的涌現，布魯姆過濾器已經越來越廣泛的應用于網絡中，例如：覆蓋網和P2P網節點協作交互、資源路由、數據幀路由標簽、網絡測量管理、網絡安全等。

目前布魯姆過濾器查詢算法主要有：標準的布魯姆過濾器算法，計數器布魯姆過濾器算法，壓縮布魯姆過濾器算法，Spectral布魯姆過濾器算法，拆分型布魯姆過濾器查詢算法，動態布魯姆過濾器算法和分檔布魯姆過濾器算法。

目前的布魯姆過濾器算法大都忽略了布魯姆過濾器可擴展性問題。現有的布魯姆過濾器大多是用固定的過濾器設計參數來表示固定的靜態集合，根據固定的集合元素規模和其在實際應用中所能容忍的最大誤判概率，確定其運算時哈希函數個數和過濾器向量的長度。因此，當集合變大時，以往大多數布魯姆過濾器的設計可能導致不能容忍的查詢誤判概率，誤判率迅速增長到1。

布魯姆過濾器可擴展性主要是當集合元素動態增長超出過濾器設計的容量時，如何調整布魯姆過濾器參數，使得布魯姆過濾器有較低的查詢誤判率，同時具有可接受的計算性能，保證過濾器的可用性。就目前的算法來說，拆分型布魯姆過濾器(Split?Bloom?filter)和動態布魯姆過濾器(Dynamic?Bloomfilter，DBF)都企圖通過將過濾器的位向量轉換為由多個位向量組成的矩陣來解決可擴展性問題，這兩種方法都是通過添加同樣大小的布魯姆過濾器向量來適應集合規模的增長。雖然這兩種方法可以有效的緩解由于集合規模的增長而導致的標準布魯姆過濾器誤判率迅速攀升。但是，這種線性擴展向量的方法在實際使用時，隨著元素個數增加，向量個數快速攀升，誤判率增長速度快，緩解程度有限。同時，此類方法的查詢時間復雜度較高，查詢的時間復雜度仍有改進的空間。

發明內容

本發明要解決的技術問題是，針對現有技術存在的缺陷，提出一種可擴展的布魯姆過濾器(Scalable?Bloom?filter，簡稱SBF)查詢方法及其元素插入方法。當集合元素不斷增長時，通過不斷增加長度成倍增長的布魯姆過濾器向量來調整查詢誤判率。并以此為基礎，給出了新的可擴展布魯姆過濾器的元素的插入、查詢方法。本發明提出的可擴展布魯姆過濾器支持集合規模的擴張，在現有的布魯姆過濾器應用領域都可以適應，如分布式計算、計算機網絡資源定位、數據庫的交互查詢、P2P網絡資源交互、傳感器網絡信息交換、計算機網絡監測、計算機緩存系統設計等產生大量數據、需要進行交互查詢的應用領域。本發明尤其適用于集合動態膨脹的應用場合，具有十分廣泛的應用前景。

本發明的解決方案是：一種可擴展布魯姆過濾器(Scalable?Bloom?filter：以下簡稱SBF)查詢方法，該方法為：

1)布魯姆過濾器的擴展：當可擴展布魯姆過濾器SBF所表示的集合元素增長超過可擴展布魯姆過濾器容量限制時，添加一個長度為前一個可擴展布魯姆過濾器向量的2倍的向量，即添加了可擴展布魯姆過濾器向量的向量長度m_i＝2m_i-1，此時添加了可擴展布魯姆過濾器向量的向量容量限制也為前一個向量容量限制的2倍，即n_i＝2n_i-1；