楊磊 黃建智

摘 要：海量數(shù)據(jù)的高效表示和查找成為目前存儲系統(tǒng)面臨的重要挑戰(zhàn).針對存儲系統(tǒng)中大規(guī)模動態(tài)數(shù)據(jù)集的表示和查找效率問題，提出一種多路平衡型矩陣Bloom Filter結(jié)構(gòu)（M-BMBF）及其插入和查詢算法.M-BMBF根據(jù)數(shù)據(jù)集合大小建立一個r×m矩陣型Bloom Filter，設(shè)計多個定位哈希函數(shù)將該矩陣Bloom Filter分為多組（多路）以實(shí)現(xiàn)平衡插入和高效查詢操作.為減緩Bloom Filter中比特的消耗速度，使用一種“最長位匹配”填充算法，新元素的插入將從多路備選Bloom Filter中選擇新置為1比特個數(shù)最少的Bloom Filter中進(jìn)行.實(shí)驗(yàn)結(jié)果表明，相較典型拆分Bloom Filter，M-BMBF能在維持算法消耗時間為常量的基礎(chǔ)上，有效節(jié)省存儲空間，降低誤判率.

關(guān)鍵詞：海量數(shù)據(jù)存儲；Bloom Filter；拆分Bloom Filter；多路平衡型矩陣Bloom Filter

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

Abstract：Aiming at solving the representation and query efficiency in massive and dynamic dataset on storage system， a Multi-group Balance Matrix Bloom Filter （M-BMBF） and the algorithms on insertion and searching of data element were proposed. M-BMBF initiates a r×m matrix Bloom filter according to the size of dataset， and it introduces multiple located hash functions which can be used to divide the matrix Bloom filter into multi-group to achieve balanced insertion and efficient query operations. In order to slow down the bits consumption rate in Bloom filter when a new element is inserted， a longest-bit match filling algorithm was proposed， which selects a Bloom filter as the destination position for insertion from the candidate Bloom filters according to the rule that fewest bits will be changed due to this insertion operation. Experiment results show that compared with the classical Split Bloom Filter， M-BMBF can efficiently save storage space and decrease the misjudgment rate， while its time consume is constant.

Key words：mass data storage； Bloom Filter；split Bloom Filter ；M-balance matrix Bloom Filter

隨著企業(yè)和個人數(shù)據(jù)的迅速增長，對于數(shù)據(jù)中心的存儲能力及管理要求也越來越高，如今，在計算機(jī)應(yīng)用中的許多基本問題都涉及到信息的表示和查詢.檢測一個元素是否屬于某個集合是最困難的任務(wù)之一，尤其是當(dāng)要被處理的數(shù)據(jù)量很大時.

Bloom Filter[1]是一種能夠表示集合并且支持集合快速查詢的簡單數(shù)據(jù)結(jié)構(gòu)，它能夠在容忍很小誤判的情況下極大地節(jié)省查詢集合的存儲空間.Bloom Filter已經(jīng)廣泛應(yīng)用于各個領(lǐng)域，如數(shù)據(jù)庫應(yīng)用[2] 、P2P網(wǎng)絡(luò)節(jié)點(diǎn)交互[3-5] 、資源路由[6]等.此外，Bloom Filter在利用較少的空間表示集合方面還有很大的應(yīng)用潛力.

近些年來，針對不同的應(yīng)用需求，對Bloom Filter做出了許多實(shí)質(zhì)性的改進(jìn).計數(shù)Bloom Filter解決了集合中元素的刪除 [7] 以及多維集合元素的高效表示和查詢問題[8]；壓縮Bloom Filter[9]減少了Bloom Filter在傳輸中所消耗的帶寬；光譜Bloom Filter[10]、拆分Bloom Filter[11]以及動態(tài)Bloom Filter[12]解決了集合中元素增長的問題；SKIP Bloom Filter[13]解決了數(shù)據(jù)流的動態(tài)特性問題；Ternary Bloom Filter在計數(shù)Bloom Filter的基礎(chǔ)上降低了誤判率[14].

前述方法多面向網(wǎng)絡(luò)應(yīng)用，側(cè)重于增強(qiáng)集合的可擴(kuò)展性、控制誤判率、控制帶寬以及元素刪除，而缺乏對檢索存儲系統(tǒng)中大容量可變數(shù)據(jù)集時高查詢性能和減少內(nèi)存開銷等需求的考慮.對于大數(shù)據(jù)存儲系統(tǒng)而言，為了能夠更快地檢索數(shù)據(jù)，減少系統(tǒng)開銷，通常選擇將索引表置于內(nèi)存甚至cache中，雖然Bloom Filter由于其所占空間非常小而可以常駐內(nèi)存，從而加快集合中數(shù)據(jù)的檢索速度，但是隨著數(shù)據(jù)量的增加，所需Bloom Filter個數(shù)也增加，最終會導(dǎo)致內(nèi)存達(dá)到瓶頸.

針對以上問題，本文提出了多路平衡型矩陣Bloom Filter算法（M-BMBF）.所謂平衡，即能夠均勻地使用每個Bloom Filter的存儲空間，為了達(dá)到平衡，M-BMBF改變了Bloom Filter的判滿條件，由原來的插入元素數(shù)量達(dá)到上限值時為滿改為Bloom Filter的使用空間達(dá)到50%時即為滿.當(dāng)插入數(shù)據(jù)時，M-BMBF引入多路（個）定位哈希函數(shù)將矩陣Bloom Filter分為多組，同時采用“最長位匹配”填充算法快速定位元素應(yīng)該具體插入的Bloom Filter，通過降低Bloom Filter空間的使用速度來提高Bloom Filter的利用率，從而可以存儲更多的數(shù)據(jù)，提高數(shù)據(jù)的檢索速度.

本文第一部分介紹相關(guān)工作，第二部分描述算法設(shè)計細(xì)節(jié)，第三部分給出實(shí)驗(yàn)評估結(jié)果，最后一部分進(jìn)行總結(jié).

1 相關(guān)工作

Bloom Filter是由Burton Bloom于1970年基于數(shù)據(jù)庫應(yīng)用程序而提出的，Bloom Filter的基本原理是通過一個長度為m的位向量來表示元素集合S={x1，x2，…，xn}，其中集合S包含有n個元素，向量中的每一位初始狀態(tài)都為0，對于集合中的每一個元素，都使用k個哈希函數(shù)把它映射到向量中，將哈希值相應(yīng)的位置置1，其他的位保持0不變.當(dāng)要查詢一個元素是否屬于某個集合時，分別使用k個哈希函數(shù)對該元素進(jìn)行計算，檢查每一個哈希值在向量中對應(yīng)的位置是否為1，只要某個哈希值在向量中的位置為0，那么就可以判定該元素不屬于集合，否則以一定的誤判率認(rèn)為該元素屬于集合.Bloom Filter的算法結(jié)構(gòu)如圖1所示.

Bloom Filter由于其簡潔高效，最近在網(wǎng)絡(luò)和存儲領(lǐng)域上受到廣泛關(guān)注[10，15-17]，使用Bloom Filter時主要考慮誤判率、內(nèi)存大小、需要管理的集合數(shù)目等性能參數(shù).

雖然Bloom Filter是一種高效的檢索數(shù)據(jù)結(jié)構(gòu)，但它還不能較好地解決諸如集合元素的動態(tài)增長和改變等問題.隨著集合中元素的增加，單個Bloom Filter的誤判率會增大，最終將導(dǎo)致Bloom Filter失效.近年來，針對動態(tài)集合的問題，對Bloom Filter作出了一些實(shí)質(zhì)的改進(jìn)，產(chǎn)生了拆分Bloom Filter算法[10]和動態(tài)Bloom Filter算法[11]以及基于這兩種算法的改進(jìn)算法.拆分Bloom Filter和動態(tài)Bloom Filter的區(qū)別在于 ：拆分Bloom Filter的基本思想是使用r個位向量來表示數(shù)據(jù)集合，當(dāng)集合中的元素個數(shù)增大到一定程度，影響到最初設(shè)計的誤判率指標(biāo)時，重新生成一個r×m的二維位向量，如果增加的元素并未達(dá)到預(yù)先給定的集合個數(shù)最大值，則隨機(jī)選擇一個位向量表示該元素.而動態(tài)Bloom Filter是根據(jù)元素的增長而動態(tài)地增加Bloom Filter，預(yù)先設(shè)計好Bloom Filter所能存儲的元素個數(shù)，初始化Bloom Filter個數(shù)為1，動態(tài)Bloom Filter只能在最后一個Bloom Filter進(jìn)行元素的插入（前提是其未滿，否則動態(tài)增加Bloom Filter）.雖然拆分Bloom Filter和動態(tài)Bloom Filter解決了元素動態(tài)增長的問題，但它們并沒有有效解決單個Bloom Filter空間利用率的問題.同時，這些算法又帶來了新的問題，在元素的查詢性能方面，它們與Bloom Filter時間復(fù)雜度為常數(shù)相違背.標(biāo)準(zhǔn)Bloom Filter的時間復(fù)雜度為O（k），而拆分Bloom Filter和動態(tài)Bloom Filter由于在插入和查詢數(shù)據(jù)時需要順序查找每個Bloom Filter，所以其時間復(fù)雜度與Bloom Filter個數(shù)有關(guān)，即O（kr），其中r為Bloom Filter個數(shù).當(dāng)Bloom Filter的數(shù)量很大時，查詢性能較差.矩陣Bloom Filter[15]基于拆分Bloom Filter的查詢性能作了改進(jìn)，通過一個特殊的哈希函數(shù)快速定位到某個Bloom Filter，并在這個Bloom Filter中對元素進(jìn)行查找或插入操作.Yi等提出了Par-BF[16]，通過并行處理的方式快速匹配元素.魏建生等人提出了動態(tài)布隆過濾器陣列（DBA）[17]，DBA由可創(chuàng)建的動態(tài)布隆過濾器組構(gòu)成，以按需調(diào)整索引容量，通過并行計算的方式處理集合中的元素，在提高元素查詢性能的同時也提高了內(nèi)存空間效率.這三種算法雖然使用不同的方法提高了元素查詢效率，但是它們并未改善Bloom Filter的空間利用率.為了解決Bloom Filter空間利用率的問題，王勇等人[18]提出了支持屬性刪減的布魯姆過濾器矩陣多維元素查詢算法CBFM，具有較高的內(nèi)存利用率；孫智超等人針對動態(tài)Bloom Filter提出了二路平衡動態(tài)Bloom Filter （2BDBF）[19]，該算法不再使用插入元素計數(shù)作為Bloom Filter的判滿條件，而是引進(jìn)了飽和度的概念，使用飽和度作為Bloom Filter的判滿條件，并且通過向量組的方式動態(tài)增長Bloom Filter，選擇向量組中空間使用最少的Bloom Filter作為元素插入位置以達(dá)到插入更多元素的效果.雖然2BDBF能夠表示更多的元素，但其查詢性能并未得到改善.

2 多路平衡型矩陣Bloom Filter

2.1 算法設(shè)計思想

如前文所述，本文工作主要基于使用Bloom Filter表示動態(tài)數(shù)據(jù)集時的插入查詢效率和空間使用效率展開，設(shè)計了一種多路平衡型矩陣Bloom Filter過濾器（M-BMBF），其算法設(shè)計結(jié)構(gòu)如圖2所示.

為解決動態(tài)數(shù)據(jù)集的插入和查詢效率問題，M-BMBF引入了多個定位哈希函數(shù)概念.M-BMBF的基本設(shè)計思想是將動態(tài)集合表示成一個r×m的位矩陣.該矩陣的行為r，表示有r個Bloom Filter；列為m，表示每個Bloom Filter的向量長度為m比特.在這里行為r是一個常量，必須按照對集合尺寸的最大值估計而預(yù)先確定.為了提高元素的查找性能，本文設(shè)計s個定位哈希函數(shù)h0，h1，…，hs-1，這s個哈希函數(shù)是經(jīng)過特殊定義的并且不同于其他k個獨(dú)立的哈希函數(shù).為了降低s個哈希函數(shù)出現(xiàn)沖突的概率，將r個Bloom Filter劃分成s組，其中每組有r/s個Bloom Filter，而每個定位哈希函數(shù)映射一組Bloom Filter.在元素添加之前，需要確定該元素應(yīng)該被添加在哪一個Bloom Filter中，這時就可以使用這s個哈希函數(shù)進(jìn)行定位計算，選出該元素在每一組中所對應(yīng)的Bloom Filter作為候選插入位置.

由推論1，我們可以將Bloom Filter在最低誤判率下的最大插入元素個數(shù)轉(zhuǎn)化為其位空間的使用狀況，據(jù)此我們使用了“最長位匹配”填充算法以提高Bloom Filter的空間利用效率.“最長位匹配”填充算法的主要設(shè)計思想是如果在插入元素時，能把元素的哈希函數(shù)值盡量多地映射到Bloom Filter向量中已為1的位置上，則可能在保持p不變的前提下插入比n更多的元素.

具體來說，插入時，利用k個哈希函數(shù)計算元素x的k個哈希函數(shù)值后，將它們與候選Bloom Filter的對應(yīng)地址位置進(jìn)行比較，如果發(fā)現(xiàn)有其中一個Bloom Filter所對應(yīng)的k個哈希函數(shù)的地址都為1，則認(rèn)為該元素已存在，不需要作插入處理；否則選擇這s個候選Bloom Filter中對應(yīng)地址值為1的位置與x的k個哈希地址重合最多的作為其插入位置.在M-BMBF中，每個定位哈希函數(shù)的哈希范圍為{0，1，2，…，r/s}，而其他k個哈希函數(shù)的范圍為{0，1，…，m-1}.因此，在構(gòu)建M-BMBF之前，哈希函數(shù)的個數(shù)k并不是真正用在算法中的個數(shù)，實(shí)際上，將要使用k+s個哈希函數(shù).假設(shè)定位哈希函數(shù)是完美隨機(jī)的，這樣每一組中所能容納的元素個數(shù)應(yīng)該是相同的，為n/r.M-BMBF的算法結(jié)構(gòu)如圖2所示.

2.2 算法實(shí)現(xiàn)

如算法1所示，為了表示和查找動態(tài)集合中元素，首先要根據(jù)對集合尺寸最大值的估計而預(yù)先建立好一個r×m的矩陣Bloom Filter，并將所有的位初始化為0（參見偽代碼中的第1行）.定義s個定位哈希函數(shù)，然后根據(jù)上一節(jié)所描述的算法思想，將r個Bloom Filter劃分成s組，每組有r/s個Bloom Filter，每個定位哈希函數(shù)通過對第一組哈希函數(shù)的映射再偏移的方式對應(yīng)映射到相應(yīng)的組Bloom Filter中（參見偽代碼中的第5行）.

對于元素的插入過程，首先計算s個哈希函數(shù)，找出每一組中具體映射到的Bloom Filter作為備選插入位置，然后對該元素進(jìn)行k個相互獨(dú)立的哈希函數(shù)計算（參見偽代碼中的第6行），將該元素的k個哈希函數(shù)地址與備選的Bloom Filter的對應(yīng)地址位置進(jìn)行比較，找出k個哈希函數(shù)的計算中與向量中已經(jīng)為1的位置重合最多的Bloom Filter，將該元素插入到此Bloom Filter中（參見偽代碼8-11行），并將該Bloom Filter的k個哈希函數(shù)映射中剩余的未被置1的位置置為1即可（參見偽代碼12-13行）.

當(dāng)要查詢一個元素時，其過程如算法2所示.

2.3 性能分析

2.3.1 時間復(fù)雜度（元素檢索時間）

當(dāng)要查詢一個元素是否屬于某個集合時，拆分Bloom Filter和2BDBF是對每個Bloom Filter按順序依次查詢，直至查到為止，而對每一個Bloom Filter的查詢時間為O（k），其中k為哈希函數(shù)個數(shù)，那么拆分Bloom Filter和2BDBF最壞情況下的平均查詢時間為O（kr）.本文算法（如算法2）首先用s個定位哈希函數(shù)定位到相對應(yīng)的Bloom Filter組中的某一個Bloom Filter，其時間復(fù)雜度為O（s），然后在這s個Bloom Filter中進(jìn)行k個哈希函數(shù)的映射，其時間復(fù)雜度為O（k），因此，本文算法總的查詢時間復(fù)雜度為O（ks）.由于s一般遠(yuǎn)小于r，本文算法能夠有效解決查詢效率的問題.

2.3.2 誤判率分析

就Bloom Filter而言，在查詢某個元素時，如果該元素本不屬于動態(tài)集合，但在查詢過程中卻返回true，便發(fā)生誤判.由文獻(xiàn)[10]可知，拆分Bloom Filter的誤判率為：

而對于本文所提算法，當(dāng)0≤d≤s-1，假設(shè)第d個定位哈希函數(shù)對應(yīng)的Bloom Filter發(fā)生誤判的概率為fd，那么在算法的所有定位行中都不發(fā)生誤判的概率為（1-fd）s.因此，至少有一個Bloom Filter發(fā)生誤判的概率為1-（1-fd）s，故可得M-BMBF的誤判率為：

相較拆分Bloom Filter，M-BMBF的誤判率與定位哈希函數(shù)個數(shù)s有關(guān)，在插入元素相同的情況下，由于s≤r，故FM-BMBF≤F.

2.3.3 空間性能

Bloom Filter本身是一種具有高效空間表現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個集合，相比B樹和哈希表等其他與數(shù)據(jù)大小相關(guān)的數(shù)據(jù)結(jié)構(gòu)而言，所占存儲空間非常小，故可以常駐內(nèi)存.本文在多個候選Bloom Filter中選擇元素插入位置時采用“最長位匹配”填充算法，在Bloom Filter的位空間使用率達(dá)到50%之前可以插入更多的元素，從而節(jié)省Bloom Filter的存儲空間.同時，從公式（1）和公式（2）的分析可知，在變量參數(shù)m、k和r相同時，如果誤判率也控制在相等的情況下，由于s≤r，故M-BMBF插入的元素多于拆分Bloom Filter，從而可以達(dá)到節(jié)省空間的效果.

3 實(shí)驗(yàn)結(jié)果與分析

如前文所述，拆分Bloom Filter算法為動態(tài)經(jīng)典算法，2BDBF與本文算法部分思路相近，下面通過實(shí)驗(yàn)對比M-BMBF算法、2BDBF算法以及拆分Bloom Filter三種算法性能.本實(shí)驗(yàn)各算法使用Java語言編寫，在eclipse的編譯工具下編譯運(yùn)行，使用的運(yùn)行環(huán)境是Intel（R） Core（TM） Duo CPU，2.00 GB內(nèi)存和32位的Windows7操作系統(tǒng).為了進(jìn)行實(shí)驗(yàn)測試，搜集30萬個文本文件，并對這些文件進(jìn)行去重處理，取出其中的20萬個文件作為數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).在整個實(shí)驗(yàn)過程中Bloom Filter的長度m和哈希函數(shù)的個數(shù)k是固定的，其中m=131 072，k=10，由于插入元素個數(shù)n和Bloom Filter個數(shù)r以及定位哈希函數(shù)個數(shù)s是用戶可以自定義的三個參數(shù)，本文首先充分利用計算機(jī)多核CPU的計算資源，并行執(zhí)行s個定位哈希函數(shù)的計算并通過實(shí)驗(yàn)比較和分析了三種算法在元素插入個數(shù)，算法消耗時間以及誤判率三個典型指標(biāo)上的性能.

本文首先測試了取不同定位哈希函數(shù)個數(shù)s時對M-BMBF的性能影響，主要從三個方面進(jìn)行分析.如表1所示，在并行執(zhí)行多個定位哈希函數(shù)的計算時，當(dāng)定位哈希函數(shù)s發(fā)生變化，對插入元素個數(shù)以及算法的消耗時間并沒有明顯影響.之所以對算法消耗時間沒有產(chǎn)生影響，是因?yàn)?，在多核環(huán)境下，只要CPU的核數(shù)足以支撐每個定位哈希函數(shù)的獨(dú)立計算，那么元素的多個定位哈希函數(shù)計算就可以并行執(zhí)行.從表中我們還可以知道，當(dāng)定位哈希函數(shù)的個數(shù)增加時，誤判率也會隨著增加，這是因?yàn)殡S著定位哈希函數(shù)的增加，元素的查找范圍也會增大，這就會導(dǎo)致誤判的概率增大.綜合考慮，本文后續(xù)實(shí)驗(yàn)均取s=2.

為了進(jìn)一步驗(yàn)證M-BMBF算法的其它性能，取定位哈希函數(shù)個數(shù)固定為s=2，在整個實(shí)驗(yàn)過程中分別改變元素插入個數(shù)n和Bloom Filter個數(shù)r，在相同的條件下與拆分Bloom Filter、2BDBF作比較，分析三種算法的元素插入數(shù)量、算法消耗時間以及誤判率如下.

圖3給出了三種算法在存儲空間相同的情況下分別取不同的Bloom Filter個數(shù)時所能插入的元素個數(shù)情況.由圖可知，隨著Bloom Filter個數(shù)r的增加，當(dāng)Bloom Filter的空間使用達(dá)到飽和度時，拆分Bloom Filter、2BDBF和M-BMBF的元素插入個數(shù)均呈穩(wěn)定增長.從圖中同時可以看出，相較拆分Bloom Filter和 2BDBF，由于M-BMBF算法每次都選擇新置為1的個數(shù)增加最少的Bloom Filter作為元素的插入位置，減緩了達(dá)到飽和度的速度，因此在Bloom Filter個數(shù)相同的情況下，M-BMBF能夠插入的元素更多，這種增加趨勢在Bloom Filter越多時則越顯著.

圖4、圖5給出了分別改變Bloom Filter個數(shù)和元素插入個數(shù)時三種算法的消耗時間情況.圖4為取n=10 000時不同 Bloom Filter個數(shù)所帶來的算法消耗時間結(jié)果.由圖可知，當(dāng)Bloom Filter個數(shù)較少時，執(zhí)行M-BMBF算法所消耗的時間比拆分Bloom Filter和2BDBF多，這是由于當(dāng)要查詢一個元素時，M-BMBF需要計算2個額外的哈希函數(shù)，隨著Bloom Filter個數(shù)r的增加，M-BMBF算法所消耗的時間仍然趨于穩(wěn)定，而拆分Bloom Filter和2BDBF所消耗的時間卻隨之增加并超過M-BMBF，而且這種趨勢會隨著Bloom Filter個數(shù)的增多越來越大.這是因?yàn)椴鸱諦loom Filter和2BDBF的元素查找過程是逐個Bloom Filter順序查找，而采用定位哈希函數(shù)的M-BMBF卻只需要映射到相對應(yīng)的2個Bloom Filter，并對這兩個Bloom Filter進(jìn)行查找即可.圖5為固定取Bloom Filter個數(shù)r=8時三種算法隨著插入元素個數(shù)增加時的算法消耗時間結(jié)果.在Bloom Filter大小m和哈希函數(shù)個數(shù)k固定的情況下，隨著集合元素個數(shù)的增加，算法消耗的時間也逐漸增多，使用拆分Bloom Filter算法所消耗的時間與2BDBF一致，比M-BMBF算法所消耗的時間多，并且趨勢越來越大.這是因?yàn)椴樵円粋€元素時，使用M-BMBF的時間復(fù)雜度為O（2 k），而使用拆分Bloom Filter和2BDBF時最壞情況下的時間復(fù)雜度為O（kr），并且隨著集合中元素個數(shù)的增加，前兩種算法與本文所提算法之間的時間消耗差必然也會越來越大.

綜合圖4和圖5的結(jié)果和分析可知，M-BMBF的算法消耗時間優(yōu)于拆分Bloom Filter和2BDBF的算法消耗時間.

誤判率是Bloom Filter的一個重要衡量指標(biāo)，圖6給出了取Bloom Filter個數(shù)r為8時（2BDBF的組基為8）隨著插入元素的增加使用三種算法時誤判率的變化情況.如圖6所示，隨著插入元素的增加，三種算法的誤判率均隨之增加，但M-BMBF的誤判率在三種算法中是最小的，而拆分Bloom Filter是最大的，這是因?yàn)閷⑷N算法的誤判率控制在相同的情況下，使用M-BMBF和2BDBF算法能夠插入更多的元素，反過來說，當(dāng)插入元素相同的情況下，M-BMBF和2BDBF的誤判率低于拆分Bloom Filter的誤判率.同時，M-BMBF縮小了元素的查找范圍，故M-BMBF的誤判率低于2BDBF.

4 結(jié) 論

本文改變了傳統(tǒng)Bloom Filter的判滿條件，由原來的統(tǒng)計插入元素個數(shù)改變?yōu)榻y(tǒng)計Bloom Filter中已置1的位置是否達(dá)到飽和（即比例占50%），從而能夠使判滿條件更加適應(yīng)過濾器長度的變化.本文提出的M-BMBF算法在改變Bloom Filter的判滿條件的同時利用多個定位哈希函數(shù)進(jìn)行集合元素的插入和查找操作.為了減少哈希映射的沖突，將Bloom Filter進(jìn)行分組，每個定位哈希函數(shù)映射到一組Bloom Filter.理論分析和實(shí)驗(yàn)結(jié)果表明，在存儲空間有限的情況下，M-BMBF既能夠減緩空間的利用率，又能夠節(jié)省算法的消耗時間，同時能夠保持較低的誤判率.隨著存儲元素的不斷增加，當(dāng)M-BMBF設(shè)定空間無法滿足元素的表示時，需要動態(tài)地增加Bloom Filter，如果動態(tài)地增加一個M-BMBF，當(dāng)需要表示的元素數(shù)量很少時，會較大地浪費(fèi)M-BMBF的存儲空間，如果在原有的M-BMBF基礎(chǔ)上增加一組Bloom Filter，為保證負(fù)載均衡，需要重新計算s，從而增加了計算的時間復(fù)雜性，因此，如何動態(tài)增加M-BMBF的存儲空間是下一步需要研究的問題.M-BMBF的設(shè)計同時可以保證在并行環(huán)境中的高效運(yùn)行，由于高效的檢索技術(shù)對于大數(shù)據(jù)環(huán)境下的重復(fù)數(shù)據(jù)刪除是必不可少的，故接下來的工作是將所提算法應(yīng)用于典型集群文件系統(tǒng)中以實(shí)現(xiàn)重復(fù)數(shù)據(jù)檢測.

參考文獻(xiàn)

[1] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communication of the ACM， 1970，13（7）：422-426.

[2] MULLIN J K. Optional semijoins for distributed data system[J].IEEE Trans Software Eng，1990，16（5）：558-560.

[3] 朱桂明，郭得科，金士堯.ODBF：基于操作型衰落Bloom Filter 的P2P網(wǎng)絡(luò)弱狀態(tài)路由算法[J].計算機(jī)學(xué)報，2012，35（5）：911-917.

ZHU G K， GUO D K， JIN S R. ODBF：A P2P weak state routing scheme based on operative decaying Bloom filter[J].Chinese Journal of Computers，2012，35（5）：911-917.（In Chinese）

[4] LI J， TAYLOR J， SERBAN L， et al. Self-organization in peer-to-peer system[C]// Proceedings of the 10th Workshop on ACM SIGOPS European Workshop. New York： ACM， 2002：125-132.

[5] CUENA-ACUNA F M， PEERY C， MARTIN R P， et al. PlantP： using gossiping to build content addressable peer to peer information sharing communities[C]//Proc 12th IEEE International Symposium on High performance Distributed Computing. Washington： IEEE， 2003：236-249.

[6] RHEA S C， KUBIATOWICZ J. Probabilistic location and routing[C]//Proceedings of INFOCOM 2002. New York： IEEE Computer Society， 2002：1248-1257.

[7] FAN L， CAO P， J ALMEIDA J， et al. Summary cache： a scalable wide-area web cache sharing protocol[J]. IEEE/ACM Trans on Networking， 2000，8（3）：281-293.

[8] 李緯，張大方，黃昆，等. 面向大數(shù)據(jù)處理的高精度多維計數(shù)布魯姆過濾器[J]. 電子學(xué)報，2015，43（4）：652-657.

LI W， ZHANG D F， HUANG K， et al. Accurate multi-dimension counting Bloom filter for big data processing[J]. Acta Electronica Sinica， 2015，43（4）：652-657. （In Chinese）

[9] MITZENMAEHER M. Compressed Bloom filters[J]. IEEE/ACM Trans on Networking， 2002，10（5）：604-612.

[10]SAAR C， YOSSI M. Spectral Bloom filters[C]// Proceedings of ACM SIGMOD International Conference on Management of Data. San Diego： ACM Press， 2003：241-245.

[11]肖明忠，代亞菲，李曉明.拆分型Bloom Filter[J].電子學(xué)報，2004，32（2）：241-245.

XIAO M Z， DAI Y F， LI X M. Split Bloom filter[J]. Acta Electronica Sinica， 2004，32（2）：241-245. （In Chinese）

[12]GUO D， WU J， CHEN H， et al. Theory and network applications of dynamic Bloom filters[C]//Proceedings of 25th IEEE International Conference on Computer Communications. Barcelona， Catalunya： Joint Conference of the IEEE Computer and Communications Societies， 2006：23-29.

[13]唐海娜，林小拉，韓春靜. 基于移動指針的數(shù)據(jù)流冗余消除算法[J].通信學(xué)報，2012，33（2）：7-14.

TANG H N， LIN X L， HAN C J. Duplicate elimination algorithm for data streams with SKIP Bloom filter[J]. Journal on Communications， 2012，33（2）：7-14. （In Chinese）

[14]LIM H， LEE J， BYUN H， et al. Ternary Bloom filter replacing counting Bloom filter[J]. IEEE Communications Letters， 2017，21（2）：278-281.

[15]肖明忠，王佳聰，閔博楠.針對動態(tài)集的矩陣型Bloom Filter表示與查找[J].計算機(jī)應(yīng)用研究，2008，25（7）：2001-2022.

XIAO M Z， WANG J C， MIN B N. Matrix Bloom filter on dynamic set[J]. Application Research of Computers，2008，25（7）： 2001-2022.（In Chinese）

[16]LIU Y， GE X Z， DU D H C， et al. Par-BF： a parallel partitioned Bloom filter for dynamic data sets[C]//Proceedings of 2014 International Workshop on Data Intensive Scalable Computing Systems. New Orleans，Piscataway， NJ： IEEE， 2014：1-8.

[17]WEI J， HONG J， ZHOU K， et al. Efficiently representing membership for variable large data sets [J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（4）： 960-970.

[18]王勇，云曉春，王樹鵬，等. CBFM：支持屬性刪減的布魯姆過濾器矩陣多維元素查詢算法[J]. 通信學(xué)報， 2016，37（3）：139-147.

WANG Y， YUN X C， WANG S P， et al. CBFM： cutted Bloom filter matrix for multi-dimensional membership query[J]. Journal on Communications， 2016，37（3）：139-147. （In Chinese）

[19]孫智超，徐蕾.二路平衡動態(tài)布隆過濾器[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2014，44（5）：199-205.

SUN Z C， XU L. 2-balance dynamic Bloom filter[J].Mathematics in Practice and Theory， 2014，44（5）： 199-205.（In Chinese）