多路平衡型矩陣Bloom Filter

楊磊 黃建智

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

關鍵詞：海量數據存儲；Bloom Filter；拆分Bloom Filter；多路平衡型矩陣Bloom Filter

中圖分類號：TP301.6 文獻標志碼：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

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

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

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

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

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

本文第一部分介紹相關工作，第二部分描述算法設計細節，第三部分給出實驗評估結果，最后一部分進行總結.

1 相關工作

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

Bloom Filter由于其簡潔高效，最近在網絡和存儲領域上受到廣泛關注[10，15-17]，使用Bloom Filter時主要考慮誤判率、內存大小、需要管理的集合數目等性能參數.

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

2 多路平衡型矩陣Bloom Filter

2.1 算法設計思想

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

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

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

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

2.2 算法實現

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

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

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

2.3 性能分析

2.3.1 時間復雜度（元素檢索時間）

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

2.3.2 誤判率分析

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

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

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

2.3.3 空間性能

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

3 實驗結果與分析

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

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

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

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

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

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

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

4 結 論

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

參考文獻

[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網絡弱狀態路由算法[J].計算機學報，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] 李緯，張大方，黃昆，等. 面向大數據處理的高精度多維計數布魯姆過濾器[J]. 電子學報，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].電子學報，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]唐海娜，林小拉，韓春靜. 基于移動指針的數據流冗余消除算法[J].通信學報，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]肖明忠，王佳聰，閔博楠.針對動態集的矩陣型Bloom Filter表示與查找[J].計算機應用研究，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]. 通信學報， 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]孫智超，徐蕾.二路平衡動態布隆過濾器[J].數學的實踐與認識，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）