一種可擴展的布魯姆過濾器查詢方法及其元素插入方法

2023-04-23 10:23:01 1

專利名稱：一種可擴展的布魯姆過濾器查詢方法及其元素插入方法
技術領域：
本發明是涉及分布式計算技術領域，特別是涉及分布式系統產生大量數據、需要進行交互查詢的應用，具體是一種可擴展布魯姆過濾器查詢方法及其元素插入方法。
背景技術：
隨著計算技術和網際網路的高速發展，數據量不斷加大，網絡的異構性和複雜性不斷增加，日趨多樣化和複雜化的計算機環境，需要在形式、規模、功能和性能等多個層次展開計算系統的可擴展性研究。存儲系統的可擴展性是當前計算機研究的熱點。布魯姆過濾器對數據集合採用一個位串表示並能有效支持元素的哈希查找，是一種能夠表示集合、支持集合查詢的簡潔數據結構。面對不斷發展的計算機和網絡環境，數據膨脹時，研究可擴展的布魯姆過濾結構支持動態集合查詢成為布魯姆過濾器在分布式系統應用中迫切需要解決的問題。
布魯姆過濾器(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倍的向量，即添加了可擴展布魯姆過濾器向量的向量長度mi＝2mi-1，此時添加了可擴展布魯姆過濾器向量的向量容量限制也為前一個向量容量限制的2倍，即ni＝2ni-1；2)可擴展布魯姆過濾器元素查詢步驟第一步利用SBF查詢元素x是否在集合S中，令j＝i；第二步通過k個哈希函數計算x在SBFj的k個映射位，檢查所有位是否都為1；第三步所述結果為是時，元素x是SBFj表示的元素，x在集合S中，返回True；第四步所述結果為否時，元素x不是SBFj表示的元素，需要繼續檢查x是否為SBFj-1表示的元素，j←j-1，轉到2持續檢查x是否為當前向量SBFj直至j＝-1。
本發明還包括一種可擴展布魯姆過濾器的元素插入方法，若c為SBF已經表示的元素個數，則可擴展布魯姆過濾器查詢算法SBF的元素插入流程為第一步，新元素x插入SBF時，首先檢查cj=0inj]]>成不成立；第二步，如果步驟1中式成立，創建新的過濾器向量SBFi+1，通過k個哈希函數計算x在SBFi+1的k個映射位，並置位，將x插入到SBFi+1中，c←c+1，i←i+1；第三步，如果步驟1中式不成立，通過k個哈希函數計算x在SBFi的k個映射位，並置位，將x插入到當前過濾器向量SBFi中，c←c+1。
本發明提供的所述可擴展布魯姆過濾器基本原理為可擴展布魯姆過濾器SBF擴展流程為1.初始化標準布魯姆過濾器BF＝{n，m，k}，指定可以容忍的誤判率上限f0，將BF作為可擴展布魯姆過濾器的第一個過濾器向量SBF0；2.根據式n0=-ln(1-elnf0/k)mk---(1)]]>計算SBF0中最大可以表示的元素個數n0，即SBF0的容量限制，使誤判率f≤f0；3.當集合擴展到元素個數n＞n0，在SBF中添加新的長度為m1＝2×m過濾器向量SBF1；4.當集合擴展到n＞3n0，添加長度為m2＝4×m的過濾器向量SBF2到SBF中；5.集合規模n＞(2i-1)n0，SBF進行第i次擴展，添加長度mi＝2i×m的過濾器向量SBFi。
在i輪擴展後，可擴展布魯姆過濾器SBF能夠表示的集合規模為(2i+1-1)n0。
(2)上述式(2)證明如下假設可擴展的布魯姆過濾器SBF包含的過濾器向量序列為{SBF0，SBF1，SBF2，...，SBFi，...}，向量長度為m0＝m，m1，m2，...，mi，...，每個向量可以表示的最多元素個數為n0，n1，n2，...，ni，...，那麼i輪擴展後，SBF能夠表示的最大集合規模為ni_max。
SBF第一輪擴展時，長度為2×m的過濾器向量SBF1加到SBF中。為了使SBF1的誤判率f≤f0，通過式(1)，可以計算出SBF1最多能表示的元素個數n1n1=-ln(1-elnf0/k)m1k=-ln(1-elnf0/k)2mk=2n0---(3)]]>SBF算法i輪擴展時，類似於第一輪擴展的推導，可以直接計算出SBFi向量能夠表示的最多元素個數nini=-ln(1-elnf0/k)mik=-ln(1-elnf0/k)2imk=2in0---(4)]]>可擴展布魯姆過濾器經過i輪擴展後，SBF能夠最多表示的元素個數為各個向量最多表示的元素個數之和。即ni_max＝n0+n1+L+ni＝n0+2n0+L+2in0＝(2i+1-1)n0.(5)由上可知，可擴展布魯姆過濾器SBF當元素增長超過過濾器容量限制時，就產生一個新的長度為前一個布魯姆過濾器向量的2倍的向量，即新向量長度mi＝2mi-1，此時新向量容量限制也為前一個向量容量限制的2倍，即ni＝2ni-1。所以雖然布魯姆過濾器向量長度擴展按指數增長，但是，其可容納的元素個數也按指數增長，這樣一來，擴展次數減少，彌補了向量高速擴展的缺陷。
本發明提供所述可擴展布魯姆過濾器元素插入方法為令c為SBF已經表示的元素個數，則可擴展布魯姆過濾器查詢算法SBF的元素插入流程為1.新元素x插入SBF時，首先檢查cj=0inj ]]>2.是，創建新的過濾器向量SBFi+1，通過k個哈希函數計算x在SBFi+1的k個映射位，並置位，將x插入到SBFi+1中，c←c+1，i←i+1。
3.否，通過k個哈希函數計算x在SBFi的k個映射位，並置位，將x插入到當前過濾器向量SBFi中，c←c+1。
表示規模為n的動態集合時，SBF需要擴展i輪，包括L個過濾器向量，最後一個向量SBFi表示的元素個數為t個，需要存儲總空間為MSBF位，產生的查詢誤判率為fSBF，其中i＝log2(n/n0+1)(6) 和 證明如下假設SBF的初始過濾器向量為BF＝{n，m，k}。那麼經過i輪擴展後，SBF包含的過濾器向量序列的長度變化過程為m0＝m→m1＝2m0→m2＝2m1L→mi＝2mi-1隨著過濾器向量長度擴展，每個過濾器容量限制從n0到n1的變化過程為n0→n1＝2n0→n2＝2n1L→ni＝2ni-1假設規模為n的動態集合用SBF表示需要擴展i輪。根據式(5)，可以得到下面關係(2i-1)n0＝ni-1_max＜n≤ni_max＝(2i+1-1)n0(10)直接計算式(10)，擴展輪數i為log2(n/n0+1)-1≤i＜log2(n/n0+1)因為擴展輪數i應為整數，式(6)得證。
很明顯，擴展i輪後，使用可擴展布魯姆過濾表示n個元素，需要的過濾器向量個數為L＝i+1log2(n/n0+1)+1。SBF需要的空間MSBF應為各個過濾器向量SBFj(0≤j≤i空間之和MSBF＝m0+m1+L+mi＝m+2m+4m+L2im＝m(2i+1-1)(11)用式(6)中i＝log2(n/n0+1)代入式(11)，式(8)可證。
可擴展布魯姆過濾器SBF中前i個向量SBFj可以容納的元素個數為2jn0(0≤j≤i-1)，所以前i個過濾器發生查詢誤判率為fBF(mj,k,nj)=(1-e-k(2jn0)/(2jm))k=(1-e-kn0/m)k=fBf(m,k,n0).---(12)]]>從式(12)中發現前i個過濾器的查詢誤判率完全相同，最後一個過濾器向量表示的元素個數t為 最後一個過濾器發生查詢誤判率為fBF(mi,k,t)=(1-e-kt/m1)k.---(13)]]>顯然，可擴展布魯姆過濾器可能產生的誤判率為fSBF(m,k,n0,n)=1-j=0j=i-1(1-fBF(mj,k,nj))(1-fBF(mi,k,t))---(14)]]>由式(12)gBF(mj，k，nj)＝fBF(m，k，n0)和式(6)i＝log2(n/n0+1)，可擴展布魯姆過濾器SBF誤判率能直接計算為式(9)。
本發明所述可擴展布魯姆過濾器元素查詢方法的工作原理如下所述可擴展布魯姆過濾器元素查詢流程包括1.利用SBF查詢元素x是否在集合S中，令j＝i；2.通過k個哈希函數計算x在SBFj的k個映射位，檢查所有位是否都為1？3.是。元素x是SBFj表示的元素，x在集合S中，返回True；4.否。元素x不是SBj表示的元素，需要繼續檢查x是否為SBFj-1表示的元素，j←j-1，轉到2持續檢查x是否為當前向量SBFj直至j＝-1。
綜上所述，本發明主要針對布魯姆過濾器可擴展性問題，提出了一種有效的可擴展布魯姆過濾器(Scalable Bloom filter)查詢方法和元素插入方法。本發明在數據集元素個數增長的情況下，通過添加長度成倍增長過濾器向量來保持很低的誤判率。
因為目前僅存在拆分和動態兩種支持集合擴展的布魯姆過濾器查詢方法，而且兩個思路十分類似，因此下述部分從三個方面將本發明直接和動態布魯姆過濾器(DBF)算法進行比較1)誤判率假設可擴展布魯姆過濾器SBF和動態布魯姆過濾器DBF的最初過濾器向量相同都是BF，fBF和fDBF分別表示兩方法的查詢誤判率。當集合擴展到規模為N時，二者的關係為limN+1-fDBF1-fSBF=0---(15)]]>式(15)證明如下動態布魯姆過濾器誤判率和可擴展布魯姆過濾器誤判率分別為
當DBF的最後一個過濾器向量表示的元素個數到n0，SBF最後一個過濾器向量表示的元素個數到2in0時，上式可簡化為 令x=(1-(1-e-km0/m)k),]]>那麼 因為 0＜x＜1，極限為0顯然成立。
■由上述可知，隨著集合的不斷擴張，動態布魯姆過濾器的查詢誤判率增長速度遠遠大於可擴展布魯姆過濾器的查詢誤判率增長速度。即使當集合規模增長到很大時，可擴展布魯姆過濾器的查詢誤判率仍可以控制在比較小的範圍。
圖1是三種算法隨著集合的增長誤判率的比較。圖中布魯姆過濾器的初始向量長度m＝1280bit，使用哈希函數個數k＝7，過濾器設計時集合容量限制為n0＝133。從圖中可以看出，三種算法隨著元素集合增長，誤判率變化規律。當集合元素個數n＜n0時，三種算法誤判率相同。隨著元素個數增加，標準布魯姆過濾器誤判率急速增長，迅速趨向1，導致標準布魯姆過濾器不可用。使用動態布魯姆過濾器，誤判率也是隨著元素個數增加而增長，但是相對標準布魯姆過濾器來說，其增長的速度較慢，可以有效的減緩布魯姆過濾器的增長問題。而可擴展布魯姆過濾器隨著元素個數的增長，誤判率增長很慢，遠遠小於前兩種算法。
圖2是動態算法和可擴展算法的誤判率之比。計算表明，當m＝1280bit，k＝7，n0＝133，n由134擴展到6000時，動態布魯姆過濾器與可擴展布魯姆過濾器誤判率之比的平均值約為4.69，這說明可擴展布魯姆過濾器誤判率平均為動態布魯姆過濾器誤判率的21.3％。
2)查詢時間可擴展布魯姆過濾器查詢算法的平均查詢時間為O(k×lgn)(16)式(16)證明如下1、理想情況下，待查詢的元素正好表示在最後的過濾器向量SBFi，查詢元素是否在集合中只需要一次查詢過程，需要k次匹配操作。
2、最壞情況下，必須檢查所有的(i+1)過濾器向量才能完成元素是否在集合的查詢，因此需要k×(i+1)次匹配操作。
因此，使用可擴展布魯姆過濾器查詢算法的平均查詢時間為O((k+k×(i+1))/2)＝O(k×(i+2)/2)＝O(k×(log2(n/n0+1)+2)/2)＝O(k×lgn)發現可擴展布魯姆過濾器查詢時間複雜度和動態布魯姆過濾器相比明顯減少，由線性降低到對數。
圖3是三種算法隨著集合增長，查詢時間比較圖。當集合元素個數n＜n0，三種算法的查詢時間相同，都是常數k次匹配時間。標準布魯姆過濾器的查詢時間與n無關，是和x軸平行的直線，但當n很大時，誤判率會越來越高。動態布魯姆過濾器的查詢時間隨著集合元素個數線性增長，雖然n不大時，其查詢複雜度小於可擴展布魯姆過濾器，但其隨n增長的速率遠大於可擴展布魯姆過濾器。
3)存儲空間布魯姆過濾器查詢方法在分布式系統中得以廣泛應用的最大優勢在於存儲空間簡潔，本節討論動態和可擴展布魯姆過濾器存儲空間的關係。
假設可擴展布魯姆過濾器SBF和動態布魯姆過濾器DBF的最初過濾器向量相同都是BF，所需的存儲空間分別為MDBF和MSBF。當集合規模N→+∞時，下面關係成立1-MSBFMDBF2+---(17)]]>這裡1-是小於1的數，在1的左邊趨向1，2+大於2，在2的右邊趨向2。
式(17)證明如下將動態布魯姆過濾器和可擴展布魯姆過濾器存儲空間表達式進行縮放，得(N/n0)·m≤MDBF≤(N/n0+1)·mm(2log2(N/n0+1)-1)MSBFm(2log2(N/n0+1)+1-1).]]>進而m(2log2(N/n0+1)-1)(N/n0+1)mMSBFMDBFm(2log2(N/n0+1)+1-1)(N/n0)m]]>上式化簡得N/n0N/n0+1MSBFMDBF2(N/n0+1)-1N/n0=2N/n0+1N/n0]]>左邊界N/n0N/n0+11,]]>而且limN+N/n0N/n0+1=1,]]>所以1-MSBFMDBF.]]>右邊界 有類似結論。■圖4三種方法存儲空間比較，y軸表示的是存儲空間，單位bit，x軸是集合規模。標準布魯姆過濾器的存儲空間與n無關，但當n很大時，誤判率會越來越高，誤判率變得不可容忍。動態和可擴展方法的存儲空間隨著元素增長而階梯式增長，動態算法的階梯更像現實生活中的樓梯，每級相等，而可擴展布魯姆過濾器的階梯逐漸變寬，向量長度按指數階梯式增長，而跳變間隔也按指數階梯式增長，SBF算法擴展輪數遠遠小於DBF算法。
圖5進一步說明了式(17)，可擴展布魯姆過濾器最壞情況下的存儲空間不過是動態布魯姆過濾器的2倍。
由以上可知，本發明是一種有效的可擴展布魯姆過濾器(Scalable Bloomfilter)和基於此的查詢方法，在數據集元素個數增長的情況下，通過添加長度成倍增長過濾器向量來保持很低的誤判率。理論證明和實驗分析表明新的可擴展布魯姆過濾器以比動態布魯姆過濾器佔有最多兩倍的空間為代價，其元素查詢誤判率始終遠遠小於動態布魯姆過濾器，新方法查詢時間按對數增長，解決了現有算法查詢時間增長過快問題，和目前的可擴展方法相比具有很大的性能優勢。


圖1三種方法誤判率比較曲線圖；圖2誤判率之比fDBF/fSBF曲線圖；圖3三種方法查詢時間比較曲線圖；圖4三種方法存儲空間比較曲線圖；圖5SBFs和DBFs存儲空間比曲線圖；圖6H3哈希函數邏輯實現原理框圖；圖7可擴展哈希函數設計示意圖；圖8基於H3哈希函數實現的可擴展布魯姆過濾器元素插入流程圖；圖9基於H3哈希函數實現的可擴展布魯姆過濾器元素查詢流程圖；圖10可擴展布魯姆過濾器元素查詢邏輯實現示意圖。
具體實施例方式
本實施例提供一種基於H3哈希函數實現的可擴展布魯姆過濾器，其中採用的H3哈希函數是Carter和Wegman定義的一類通用哈希函數(universal Hash)。H3函數具有很強的散列性，是一種常見的布魯姆過濾器的實現函數；又因其對每個輸入元素的哈希計算僅需要簡單的「與」和「異或」運算，便於實現，尤其是硬體實現，是計算機硬體最常用的哈希函數之一。
H3哈希函數是一個線性轉換BT＝Qr×wAT，將w-bit長度的元素A＝a1a2Law轉換為r-bit的哈希地址B＝b1b2Lbr，即b1b2Mbr=q11q12Lq1wq21q22Lq2wLLLLqr1qr2Lqrwa1a2Maw]]>其中轉換矩陣Qr×w是一個0，1矩陣，每個轉換矩陣對應一個H3哈希函數，其乘法運算和加法運算分別採用二進位與AND(g)和二進位異或XOR()運算，即bi＝(a1·qu1)(a2·qi2)L(aw·qiw)(i＝1，2，L，r)如果轉換矩陣用列向量表示Qr×w＝(d1d2Ldw)，將aigdi表示成ajdj=ajq1jq2jMqrj=ajajMajq1jq2jMqrj=ajq1jajq2jMajqrj]]>那麼BT＝h(A)＝(a1gd1)(a2gd2)L(awgdw)(18)H3哈希函數示例。設w＝8，r＝2，輸入元素經哈希函數計算由{0L 255}→{0L 3}。轉換矩陣為Q28=0110110111000101,]]>則元素69和105的哈希地址可直接通過式(18)計算。
h(69)=h(01000101)=d2d6d8=111111=11,]]>11T=(11)=3(decimal)]]>h(105)=h(01101001)=d2d3d5d8=11101011=00,]]>00T=(00)=0(decimal).]]>H3哈希函數採用的是邏輯運算AND(g)和異或XOR()，便於硬體或軟體實現，如圖6所示。
H3哈希函數由W個「與門」和一個「異或門」組成，其移位器(Shifier)用於獲得輸入元素的各位，對於每個哈希函數，列向量d1，d2，L，dw∈
相互獨立，那麼「異或門」出來的結果就是哈希映射地址。
為了適應可擴展布魯姆過濾器向量長度的調整，需採用哈希地址可調的哈希函數，下面介紹可擴展布魯姆過濾器的哈希函數設計。
1.在哈希函數設計之前，定義以下參數n0初始化過濾器向量最多能容納的元素個數w集合元素的比特數m初始過濾器向量長度f0能容忍的最大誤判率N預測的集合最大規模2.令r＝log2m，並計算哈希函數個數k3.隨機產生k個R×w的0，1矩陣QR×w[1]，QR×w[2]，...QR×w[k]作為可擴展布魯姆過濾器的轉換矩陣，其中
4.採用上述矩陣的前r行組成的轉換矩陣作為元素的映射哈希函數，獲取哈希地址將SBFr-log2m向量置位5.可擴展布魯姆過濾器每擴展一次，r←r+1，轉到4基於H3哈希函數的可擴展過濾器元素插入方法為可擴展布魯姆過濾器元素插入流程如圖8所示。新元素加入時，如果是第一個元素，產生一個符合設計初始化要求的標準布魯姆過濾器，設置初始向量長度m0，最初的集合元素個數容量限制為n0，布魯姆過濾器擴展輪數為0(表明還沒有經過一次擴展)，當前活動布魯姆過濾器為剛產生的布魯姆過濾器向量，所容納的元素個數為0。新元素(element)插入時，首先需要判斷現有的過濾器所容納的元素個數是否已經達到過濾器容量限制，如超過限制，產生一個新的長度和容量均為當前活動布魯姆過濾器2倍的過濾器向量，完成過濾器擴展，過濾器總容量限制同時也應加上新增加的過濾器容量。
完成過濾器擴展操作後，新元素插入操作需要根據當前的擴展輪數，按照上節的可擴展布魯姆過濾器哈希函數設計，得到當前擴展輪數的相對應的k個H3哈希函數，然後計算出元素對應的k個向量位置，在當前活動布魯姆過濾器置位(當前活動過濾器向量總是最後一個加入的過濾器向量)，完成新元素的插入過程。
基於H3哈希函數的可擴展過濾器元素查詢方法是基於圖7的可擴展哈希函數設計，現給出由擴展後哈希地址反推到擴展前哈希地址的方法，該方法通過移位操作，由元素在最後一輪擴展的哈希地址可以一直反推到向量初始化時的哈希地址，只需一次哈希計算，便可以完成元素在各個過濾器向量的查找。
假設可擴展布魯姆過濾器j輪擴展後的哈希轉換矩陣為Q(r+j)×w[u]，元素在過濾器向量SBFi的映射地址為Addrj[u](1≤u≤k)，元素在過濾器向量SBFj-1的映射地址為Addrj-1[u](1≤u≤k)，二者的關係為Addrj-1[u]＝Addrj[u]＞＞1(1≤u≤k)(20)基於上述式(20)，可擴展布魯姆過濾器查詢算法流程可以優化為圖9所示。為了判斷元素(element)是否在集合中，首先按照最終擴展輪數計算對應的過濾器向量SBFi的k個哈希映射地址，判斷是否是最後一輪插入的元素。如是，就返回True，表明元素在集合中；如不是，將這k個地址進行移位操作，得到其在過濾器向量SBFi-1的k個映射地址，判斷是否是上一輪插入的元素，如是，表明元素在集合，否則，繼續檢查是否是再上一輪，如此循環，直至檢查完所有的過濾器向量。
式(20)能夠簡化可擴展布魯姆過濾器的軟硬體實現。查詢元素是否在集合中最壞需要檢查所有的(i+1)個過濾器向量，但是只需要計算元素在最後一個過濾器向量SBFi的哈希地址，其他的地址全都可以通過移位操作直接推導。圖10是可擴展的布魯姆過濾器元素查詢判斷邏輯實現。
基於H3哈希函數的可擴展過濾器實驗結果如下所述本實施例進行仿真實驗來驗證可擴展布魯姆過濾器查詢算法的性能，為了進行比較，本實施例具體實現了可擴展布魯姆過濾器和動態布魯姆過濾器的元素插入和元素查詢。為了簡化實驗過程，直接採用的32bit整數集合作為元素集合，數據集合的元素是由計算機隨機產生的32bit的無符號整數，元素範圍為(0，232-1)，H3哈希函數轉換矩陣由32個隨機產生的列向量組成。隨機產生32×32的轉換矩陣，作為算法實現中的哈希函數。
對於長度為m＝131072＝217的標準布魯姆過濾器，可擴展H3哈希函數的初始列向量長度為r＝17。仿真實驗在HP伺服器上進行，其具體的配置為作業系統Windows Server 2003，CPUInterXeonTM3.0GHz×2，內存2.00GBDDR。
本實施例中集合規模從1,000,000到6,000,000，哈希函數個數k＝6，k＝8和k＝11。對每一種算法參數組合進行100次實驗。實驗過程分為兩步首先按照圖8、圖9完成集合元素插入，元素插入過程中，根據需要添加新的過濾器向量，完成過濾器算法的擴展；當所有的元素都映射到兩種過濾器算法之後，可以直接獲得兩算法的存儲空間。
第二步驟，實現查詢算法，評估查詢誤判率和查詢時間。為了得到查詢誤判率，採取100,000個不在集合中的元素完成布魯姆過濾器查詢，進行誤判數目統計。如果所需查找元素的對應k個映射位置均為1，表明該元素在集合中，這就出現了誤判，因為這100,000個元素都是不在集合中的元素。計算誤判率為累計誤判元素的個數和不在集合中元素總數的比值。同時，我們採取直接在SBF和DBF代碼中加入計時器的方法獲得100,000個元素的查詢總時間。
對於上述實驗過程，每個實驗參數的組合，隨機產生100次數據集合，完成100次實驗，實驗結果取100次的平均值。

從表中，發現1.實驗獲得的誤判率和理論計算值相當一致。
2.當初始過濾器向量m＝131072bit，n0＝8192，集合規模擴展到n＝1,000,000，SBF
2.當初始過濾器向量m＝131072bit，n0＝8192，集合規模擴展到n＝1,000,000，SBF算法需要進行6次擴展，共需16,646,144bit，而DBF算法需要進行122次擴展，共需16,121,856bit。SBF算法比DBF算法消耗稍多的空間，但是和DBF算法相比，誤判率降低18倍，查詢時間降低到一半。
3.當集合規模n＝1,000,000，哈希函數個數k＝11，SBF算法的查詢誤判率為0.003051，而DBF算法的誤判率為0.054475，是SBF算法的18倍。當集合規模n＝6,000,000是最初設計容量n0＝8192的732倍時，仍然採用哈希函數個數k＝11，SBF和DBF算法的查詢誤判率分別為0.004389和0.285391，此時DBF算法的誤判率時SBF算法的65倍。隨著集合的增長，DBF查詢誤判率增長速度大大超過SBF。
4.使用SBF算法查詢100,000個元素僅需要2秒左右，那麼在3GHz的機器中，一次元素查詢只需要20μs，查詢時間在實際應用中是可以接受的。
權利要求
1.一種可擴展布魯姆過濾器查詢方法，其特徵在於，該方法為1)布魯姆過濾器的擴展當可擴展布魯姆過濾器SBF所表示的集合元素增長超過可擴展布魯姆過濾器容量限制時，添加一個長度為前一個可擴展布魯姆過濾器向量的2倍的向量，即添加了可擴展布魯姆過濾器向量的向量長度mi＝2mi-1，此時添加了可擴展布魯姆過濾器向量的向量容量限制也為前一個向量容量限制的2倍，即ni＝2ni-1；2)可擴展布魯姆過濾器元素查詢步驟第一步利用SBF查詢元素x是否在集合S中，令j＝i；第二步通過k個哈希函數計算x在SBFj的k個映射位，檢查所有位是否都為1；第三步所述結果為是時，元素x是SBFj表示的元素，x在集合S中，返回True；第四步所述結果為否時，元素x不是SBFj表示的元素，需要繼續檢查x是否為SBFj-1表示的元素，j←j-1，轉到2持續檢查x是否為當前向量SBFj直至j＝-1。
2.一種如權利要求1所述可擴展布魯姆過濾器查詢方法的元素插入方法，其特徵在於，若c為SBF已經表示的元素個數，則所述可擴展布魯姆過濾器SBF查詢方法的元素插入流程為第一步，新元素x插入SBF時，首先檢查cj=0inj]]>成不成立；第二步，如果步驟1中式成立，創建新的過濾器向量SBFi+1，通過k個哈希函數計算x在SBFi+1的k個映射位，並置位，將x插入到SBFi+1中，c←c+1，i←i+1；第三步，如果步驟1中式不成立，通過k個哈希函數計算x在SBFi的k個映射位，並置位，將x插入到當前過濾器向量SBFi中，c←c+1。
全文摘要
本發明提供一種可擴展布魯姆過濾器(Scalable Bloom filter)查詢方法，在數據集元素個數增長的情況下，通過添加長度成倍增長過濾器向量來保持很低的誤判率，並給出了一種可擴展布魯姆過濾器查詢方法的元素插入方法。實驗表明，可擴展布魯姆過濾器的元素查詢誤判率永遠小於動態布魯姆過濾器，可以控制查詢誤判率在1％，在3.0GHz的CPU機器中，一次元素查詢時間僅20μs，比DBF查詢速度快很多倍。本發明在現有的布魯姆過濾器應用領域都可以適應，由於支持集合的動態擴展，因此比現有的布魯姆過濾器具有更加廣泛的應用前景。
文檔編號G06F17/30GK101082923SQ20071003538
公開日2007年12月5日 申請日期2007年7月18日 優先權日2007年7月18日
發明者謝鯤, 閔應驊, 張大方, 文吉剛, 謝高崗 申請人:湖南大學