CBFM：支持屬性刪減的布魯姆過濾器矩陣多維元素查詢算法

王勇，云曉春,2，王樹鵬，王曦

?

CBFM：支持屬性刪減的布魯姆過濾器矩陣多維元素查詢算法

王勇1，云曉春1,2，王樹鵬1，王曦1

（1. 中國科學院信息工程研究所北京 100093；2. 國家計算機網絡應急技術處理協(xié)調中心北京 100029）

為了提升多維元素成員查詢的靈活性和準確率，提出了一種新型索引結構CBFM(cutted Bloom filter matrix)。該索引方法通過獨立屬性布魯姆過濾器笛卡爾乘積構建位矩陣，支持任意屬性組合的多維元素成員查詢，同時支持屬性組合按需刪減和屬性加權，極大地提升內存空間利用率，降低查詢誤判率。理論分析證明相比于BFM(Bloom filter matrix)索引方法，CBFM具有更高的內存利用率。仿真實驗表明，在分配內存相同的情況下，CBFM方法相比于其他方法，具有最低的查詢誤判率，特別在內存受限場景下，CBFM相比于BFM方法，查詢誤判率最大降低3個數(shù)量級，極大地提升了多維元素成員查詢的準確率。

查詢算法；多維元素成員查詢；布魯姆過濾器；位矩陣

1 引言

隨著移動互聯(lián)網、Web2.0等相關產業(yè)的快速發(fā)展，數(shù)據逐漸呈現(xiàn)出規(guī)模巨大化、類型多樣化、流量高速化等大數(shù)據[1]特征，數(shù)據多維特征日趨明顯，海量多維數(shù)據的存儲、計算及實時分析為信息系統(tǒng)帶來嚴峻的挑戰(zhàn)。多維元素成員查詢，是一種判斷特定對象是否存在于目標數(shù)據集的重要手段，在數(shù)據集上進行全維度或部分維度查詢并得到true/false的回答，廣泛應用于分布式云存儲[2~6]、網絡監(jiān)控及測量[7]等系統(tǒng)中。

在分布式云存儲系統(tǒng)中，面對PB級數(shù)據量、數(shù)萬屬性的數(shù)據管理需求，Google BigTable[2]、HBase[3]等云存儲系統(tǒng)，在進行數(shù)據操作之前，都需要在分布式節(jié)點上進行成員查詢以便于定位目標數(shù)據；在MapReduce[4]、Hive[5]、Impala[6]等并行計算系統(tǒng)中，通過多維元素成員查詢，可以實現(xiàn)本地分區(qū)多維數(shù)據塊的快速存在性檢測，極大地降低本地分區(qū)數(shù)據塊的磁盤掃描時間，提升查詢效率。在網絡監(jiān)控及測量應用中，由于TCP協(xié)議超時重傳及路由器可能的故障重復轉發(fā)等原因，大量重復數(shù)據產生，導致在其之上的數(shù)據查詢及分析不可信，通過多維元素成員查詢，可以有效地進行網絡流數(shù)據重復檢測等預處理[7]，以便實現(xiàn)高效的網絡傳輸及在線數(shù)據分析。

多維元素成員查詢典型解決方案包括表索引[8,9]、樹索引[10,11]及布魯姆過濾器[12]索引結構。其中，表索引[8, 9]將多維元素存在于表中，其最大缺點是內存占用較高；樹索引結構[10,11]能夠支持元素查詢的多維性，但是其面向異構數(shù)據集的結構負載均衡難度較大，而且應用集成復雜性較高；布魯姆過濾器[12]是一種可以高效表示數(shù)據集合并進行存在性判斷的數(shù)據結構，其核心優(yōu)點是具備較高的空間效率和查詢效率，但其不支持任意屬性組合查詢，MDBF[13]、CMDBF[14]對布魯姆過濾器進行了多維擴展，但是其針對支持任意屬性組合的元素成員查詢存在較高的誤判率，尤其對于屬性相關性較高的數(shù)據集表現(xiàn)并不理想；BFM算法[14]是目前較為經典的布魯姆過濾器多維擴展方法，支持任意屬性組合多維元素成員查詢，查詢誤判率也相對較低，但是其內存利用率較低，且無法支持屬性權重的差異化處理。綜上所述，多維元素成員查詢的核心技術在于多維索引的構建，其應該具備查詢模式自由(schema-free)能力，即支持任意屬性組合的元素成員查詢，同時應具備較高的內存空間利用率、較低的查詢誤判率和屬性權重差異化處理能力。

本文提出了一種新型索引結構CBFM（cutted Bloom filter matrix），該索引方法通過獨立屬性布魯姆過濾器笛卡爾乘積構建位矩陣，支持任意屬性組合的多維元素成員查詢，同時支持屬性組合按需刪減和屬性加權，極大地提升內存空間利用率，降低查詢誤判率。本文的貢獻可以歸納為如下內容。

1) 結合多維元素成員查詢的相關研究現(xiàn)狀，給出此問題的形式化定義，并在此基礎上，提出了一種新型索引結構CBFM，CBFM支持任意屬性組合的多維元素成員查詢，并通過屬性組合按需刪減和屬性加權的方式提升內存空間利用率，降低查詢誤判率。

2) 理論分析證明了CBFM索引方法的內存空間高效性。相比于BFM索引方法，CBFM在期望誤判率一致的前提下，通過維度刪減的方式大幅降低內存空間占用。

3) 針對CBFM方法進行了充分的仿真實驗，在查詢誤判率、內存空間占用、維度擴展性等方面與相關研究工作進行充分比較，實驗數(shù)據表明，在分配內存相同的情況下，CBFM具有最低的查詢誤判率，特別在內存受限場景下，CBFM相比于BFM，查詢誤判率最大降低3個數(shù)量級。同時CBFM具備較好的維度擴展能力。

2 相關研究工作

多維元素成員查詢典型解決方案包括表索引、樹索引及布魯姆過濾器索引結構，其中，布魯姆過濾器以其較高的空間利用率及查詢性能等優(yōu)勢應用較廣，下面首先介紹布魯姆過濾器及其多維擴展。

2.1 布魯姆過濾器

標準布魯姆過濾器[12]SBF由一個位向量和一組散列函數(shù)構成，如圖1所示。假設數(shù)據集合總計個元素，所有元素均通過個散列函數(shù)映射到長度為的位向量中。當進行元素插入時，對于每一個元素，計算，將置位為1；當進行元素查詢時，對于給定元素，檢查位向量的個位置，若所有位置均判斷為1，則判定可能在集合中，否則一定不在集合中。

綜上所述，標準布魯姆過濾器存在一定的假陽性概率(false positive rate)，即不屬于集合中的元素可能被判定為屬于此集合。

2.2 布魯姆過濾器多維擴展

標準布魯姆過濾器SBF不支持多維元素成員查詢，Guo等[13]提出了一種多維布魯姆過濾器算法MDBF，算法核心思想是針對多維數(shù)據集的每一個屬性，構建獨立的布魯姆過濾器，當查詢元素時，通過判斷多維元素的各個屬性值是否都存在于相應的布魯姆過濾器，來判斷元素是否屬于集合。CMDBF[14]在MDBF基礎上新增一個用于表示元素整體的聯(lián)合布魯姆過濾器CBF，并將元素表示和查找分2步進行，將MDBF各屬性的表示和查詢作為第1步，第2步聯(lián)合元素所有屬性域，利用CBF完成元素整體的表示和查詢確認。在配置參數(shù)為{,,,}情況下，CMDBF查詢誤判率為，略低于MDBF查詢誤判率。

MDBF、CMDBF均未能有效解決多維元素成員查詢場景下的任意屬性組合查詢問題，文獻[14]提出了一種布魯姆過濾器矩陣算法(BFM)，該算法在每個維度上保存一個位向量以構建布魯姆過濾器，并基于獨立屬性笛卡爾乘積構建位矩陣，用于全屬性組合查詢，從根本上消除了組合誤差率；同時，BFM在獨立屬性位向量上添加1個標記位，以支持任意屬性組合查詢。實驗證明BFM索引方法在高相關性數(shù)據集場景下，具備相對較低的查詢誤判率，是目前應用較廣的多維元素成員查詢算法。然而，隨著數(shù)據集維度數(shù)的增加，算法內存空間占用呈指數(shù)級增長，且查詢誤判率會隨所查詢屬性數(shù)目減少而大幅提升。

與文獻[15]不同，文獻[16]提出了布魯姆過濾器笛卡爾聯(lián)接索引算法(CBF)，該索引方法僅存儲全屬性位矩陣信息，不維護特殊標記位，在非完整屬性集上采用遍歷的方法，因此其內存空間利用率稍好于BFM方法，但是在任意屬性組合查詢及查詢效率方面略顯不足。

2.3 其他相關研究工作

除布魯姆過濾器及其多維擴展外，多維元素成員查詢典型解決方案包括表索引[8,9]、樹索引[10,11]及混合索引[18,19]結構等。

文獻[8]提出一種應用于ZFS分布式文件系統(tǒng)的表索引方案，將多維元素存儲于表中以實現(xiàn)成員查詢，其最大的不足是內存占用偏高，而且查詢復雜度較高（或）；緊湊型散列表[9]可以在一定程度上提升查詢效率，并降低內存占用，但同時固化了查詢模式。

在樹索引研究方面，Zhou等[10]提出了一種雙層索引算法EDMI，算法核心思想如下：全局索引層采用KD樹進行子空間劃分，局部索引層針對每個子空間，采用ZPR樹進行數(shù)據索引。MD-HBase[11]提出了一種基于空間目標排序的多維索引算法，其核心思想是采用Z排序技術對多維空間目標進行排序，以Z-Value作為每條記錄的鍵值，并在此基礎上利用KD樹或四叉樹對多維數(shù)據空間進行劃分，并計算各子空間最長公共前綴作為索引項，以支持數(shù)據內容查詢。樹結構索引算法較好地解決了元素查詢的多維性，但是其空間復雜度較高，而且結構負載不均對整體查詢性能存在較大影響。

目前廣泛應用的混合索引結構是將布魯姆過濾器與樹索引進行融合。Adina等[18]在2015年提出了一種混合索引結構Bloofi，將B+樹和布魯姆過濾器進行層次化融合，并在此基礎上實現(xiàn)位級別的并行化算法Flat-Bloofi，有效解決了多維數(shù)據集的元素查詢問題。為了解決云存儲環(huán)境下的非KEY字段查詢問題，BF-Matrix[19]提出了一種層次化索引結構，結合了布魯姆過濾器和B+樹，極大縮減了元素查詢路徑，并采用基于規(guī)則的索引更新機制，有效降低布魯姆過濾器的假陰性概率。

3 CBFM設計

3.1 形式化定義

本文在上述研究工作的基礎上給出了多維元素成員查詢的形式化定義。假設數(shù)據集合總計個元素，其中，任一數(shù)據項均為多維對象,由個不同屬性構成,即。

基于應用場景差異，多維元素成員查詢支持2種查詢模式。針對全屬性查詢模式，查詢元素內容；任意屬性組合查詢模式，查詢元素內容。多維元素成員查詢返回true/ false的結果，返回true；返回false。

3.2 CBFM算法

CBFM索引方法，通過獨立屬性布魯姆過濾器笛卡爾乘積構建位矩陣，支持任意屬性組合的多維元素成員查詢，同時支持屬性組合按需刪減和屬性加權，極大的提升內存空間利用率，降低查詢誤判率。其相關運行參數(shù)如表1所示。

表1 CBFM運行參數(shù)

為了保證多維元素成員查詢場景下屬性值的完整性，CBFM在每個屬性上均采用一個獨立的位向量，并采用位矩陣存儲所有屬性關聯(lián)信息，極大地降低了組合誤差率；同時支持刪減不需要的屬性組合，提升內存空間利用率。索引結構如圖2所示。

由圖2(a)所示，CBFM在不刪減屬性組合情況下，與BFM索引方法一致，保存一個全屬性矩陣；圖2(b)顯示了刪減屬性組合的結構，二維矩陣和三維矩陣的存儲空間被極大地釋放，同時不影響所有單屬性及其他屬性組合的成員查詢。圖3給出了CBFM插入一個二維元素(A, A)的示意。

CBFM索引結構在默認情況下，所有屬性權重相等，位向量大小保持一致。為了更好地支持多維元素成員查詢場景下屬性權重的差異性，CBFM可以擴展為加權模型（WCBFM-Weighted CBFM），即可以針對重要屬性或屬性組合，分配相對較大的內存空間，進一步降低查詢誤判率。

CBFM多維元素插入算法流程如圖4所示。新元素插入時，首先拆分多維元素的各屬性值，采用散列函數(shù)進行置位計算；其次，針對每個散列函數(shù)，聯(lián)合各屬性值的散列置位結果值，計算位矩陣邏輯下標；然后，基于已刪減屬性組合信息，將邏輯下標轉換為實際位矩陣下標；最后在CBFM中進行置位，完成數(shù)據插入。

算法1 elementInsert(Object Element)輸入:待插入的多維元素A=(a1,a2,…,ad)輸出:VOIDbeginassign 0 to ResultArray;for each attribute ax in A { for each hashFunction hashx in HashSet { record hashx(ax) to hashPerField[][];} //針對每個屬性計算k次散列} //end forfor each DC of (2d?1) combinations { for each hash value hashV in hashPerField { //調用calculateIndex計算實際索引下標 invoke calculateIndex(DC, hashV, ResultArray);}} //end for//采用實際索引下標對位數(shù)組進行置1處理for each idx of ResultArray { set bit of ResultArray [idx] to 1} //end forend elementInsert

CBFM多維元素成員查詢算法流程如圖5所示。對于待查詢多維屬性組合，如果其中包含已刪減屬性組合，需要進行拆分查詢。本算法采用迭代的方式進行屬性拆分。

算法2 elementSearch(Object Element)輸入:待查詢的多維元素A=(a1,a2,…,ad), 其對應維度組合SDC，非必選字段值為null輸出:元素是否存在beginassign 0 to ResultArray;for each field ax in A { for each hashFunction hashx in HashSet { record hashx(ax) to hashPerField[][];} //針對每個屬性計算k次散列} //end forfor each EDC(does not match any dimension combinations to cut off) of SDC { for each hash value hashV in hashPerField { //調用calculateIndex計算實際索引下標 invoke calculateIndex(EDC, hashV, ResultArray);}} //end forfor each idx of ResultArray { if bit of ResultArray [idx] equals to 0 { return FALSE;}} //end forreturn TRUE;end elementSearch

3.3 模型復雜度分析

根據布魯姆過濾器基本原理得知，假設散列取值服從均勻分布，當集合中所有元素都映射完畢后，查詢誤判率為[17]

假設期望誤判率和期望元素數(shù)已經固定，在此基礎上計算散列函數(shù)個數(shù)和位向量的最優(yōu)解為

(2)

因此，CBFM實際位向量大小如式(4)所示，相比于BFM索引方法的內存空間占用m，具備相對較低的內存占用。

當進行多維元素成員查詢時，針對待查詢維元素，CBFM算法首先應用個散列函數(shù)對非空字段進行散列計算，次數(shù)上限為；其次，算法根據個已刪減維度組合將待查詢維度進行拆分，最多得到個非重復維度組合，針對每個查詢維度組合信息，算法由高到低遍歷其中每一個維度，通過枚舉相對刪減維度組合，計算當前維度中特殊標記位與非特殊標記位中的實際位個數(shù)（如圖6所示），運算次數(shù)上限為，綜上所述，CBFM元素查詢時間復雜度上限為。在實際應用中，維度數(shù)和散列函數(shù)個數(shù)都是確定的，算法的查詢時間復雜度為常數(shù)，而且與數(shù)據集大小之間并無相關性。

算法3 calculateIndex(Object DC, Object hashV, Object ResultArray)輸入:插入元素A=(a1,a2,…,ad)的一種維度組合; 使用某散列函數(shù)計算出每個字段的散列值數(shù)組; 需要置位的位索引數(shù)組輸出:VOIDbeginif DC match some dimension combinations to cut off { end calculateIndex; //維度組合與刪減組合一致}assign 0 to currentBitIndex;//由高位至低位遍歷DC中的每個維度信息for each dimension ax in DC(from high to low) { //將ax按照特殊位和非特殊位獨立處理 split ax to special bit array and normal bits array; calculate non-bulk offset in special bit array, and add it to currentBitIndex;calculate non-bulk offset in normal bits array, and add offset*(hashV[ax]?1) to currentBitIndex;} //end foradd currentBitIndex to ResultArray;end calculateIndex

3.4 數(shù)值示例

表2和表3給出二組數(shù)值示例，它們分別對比了BFM和CBFM算法，隨著期望誤判率的變化，期望元素數(shù)和期望內存空間占用的變化趨勢。在表2中，預設總可用內存大小為1 MB，期望誤判率從10?1變化到10?5，在三維數(shù)據集場景下，CBFM刪減2個兩屬性組合(0x5代表刪減維度1、3；0x3代表刪減維度1、2)，CBFM期望元素個數(shù)始終是BFM的14倍以上，這也預示著CBFM在查詢誤判率上的優(yōu)勢。在表3中，期望插入元素數(shù)=1 000，CBFM內存占用比BFM低3個數(shù)量級以上，間接反映了CBFM索引方法具備相對較高的內存空間利用率。

表2 期望元素數(shù)量對比(M=1 MB)

表3 期望內存空間占用對比(n=1 000)

4 仿真實驗

本節(jié)通過仿真實驗測試CBFM索引結構在不同屬性組合場景下的查詢誤判率、查詢效率、內存空間占用等核心指標，并與SBF、MDBF、CMDBF、BFM、CBF等索引算法進行比較。

4.1 查詢誤判率

本文分別在全屬性查詢、兩屬性查詢場景下，對比了SBF[12]、MDBF[13]、CMDBF[14]、CBF[15]、BFM[16]、CBFM這6種索引結構，其中，CBFM索引結構刪減了一個兩屬性組合。

實驗1 構造數(shù)據集驗證查詢誤判率

在實驗中，采用三維布魯姆過濾器陣列，當數(shù)據插入時，每一屬性值均采用獨立的數(shù)據集合，其值為計算機隨機構造出的32位無符號整數(shù)，取值范圍為{0,232?1}。在進行多維元素成員查詢時，首先確保所有待查詢多維數(shù)據與已存儲數(shù)據集不重復；同時，為了體現(xiàn)所查詢數(shù)據與插入數(shù)據的相關性，本文定義了一個相關性系數(shù)，用來表示查詢數(shù)據集中重復元素的占比，因此意味著查詢數(shù)據集任一字段與插入數(shù)據集均無重疊，意味著查詢數(shù)據集所有字段均來自插入數(shù)據集。

為了公平對比，本文在上述6種索引結構中設置了相同的散列函數(shù)個數(shù)(=6)及內存空間大小(=16 MB)。由圖7(a)可以看出，在全屬性查詢模式下，SBF、BFM、CBFM、CBF索引方法具有較低的查詢誤判率，CMDBF、MDBF在相關系數(shù)逐漸增大的過程中，誤判率持續(xù)增大。尤其在相關性系數(shù)=1情況下，SBF、BFM、CBFM、CBF等索引算法的誤判率相比與CMDBF、MDBF等方法的誤判率低了3個數(shù)量級，這是因為SBF、BFM、CBFM、CBF更好地解決了組合誤差率問題。MDBF方法由于不能解決組合誤差率問題，因此隨著相關系數(shù)增大，誤判率漸趨近于1。

由于SBF、CMDBF不支持兩屬性查詢，針對MDBF、BFM、CBFM、CBF進行了誤判率實驗。由圖7(b)可以看出，BFM、CBF誤判率為最高100%，CBFM誤判率最低(約為0.21%)，相比于BFM方法低了3個數(shù)量級。這是因為CBFM刪減了2個屬性組合，相比于BFM具有更大的內存空間存儲待查詢屬性組合信息，CBFM在內存受限場景下的適應性更強，空間利用率相對更高。

實驗2 根據實際數(shù)據集驗證查詢誤判率

為了進一步驗證CBFM算法的有效性，本節(jié)采用實際數(shù)據進行測試，數(shù)據源來自運營商DNS協(xié)議通信流量，核心測試屬性為{源IP地址，目的IP地址，域名}三元組信息。在數(shù)據插入和查詢環(huán)節(jié)，分別采用真實數(shù)據集不同時間區(qū)間的流量數(shù)據。

圖8(a)展示了隨著可用內存空間變化，全屬性查詢誤判率的變化趨勢。與合成數(shù)據集測試結果類似，全屬性查詢模式下，SBF、CBFM仍然保持相對較低的誤判率，BFM算法由于存在較高的空間需求導致其位沖突率較高進而增大了誤判率。在兩屬性查詢模式下，本文采用{源IP地址，域名}屬性組合，由圖8(b)可以看出，CBFM查詢誤判率最低，相比于其他算法，其具備更高的內存空間利用率。

實驗3 屬性加權查詢誤判率測試

為了驗證屬性加權對于查詢誤判率的影響，本文針對三維度數(shù)據集下，在實驗1基礎上提升2個屬性存儲權重，降低第3個屬性存儲權重，總存儲空間不變，得到的測試結果如圖9所示。

由圖9可以看出，WCBFM（加權CBFM）在全屬性查詢、兩屬性查詢場景下，查詢誤判率均相對較低，全屬性查詢模式下誤判率降低約1.69倍，兩屬性組合查詢模式下誤判率降低2個數(shù)量級。加權CBFM索引方法為特定系統(tǒng)應用優(yōu)化提供了更大的便利，可以按照應用需求進行屬性權重指定。

4.2 查詢效率

在進行查詢誤判率實驗的同時，本文記錄了查詢過程中的耗時情況，具體實驗結果如圖10所示。

由圖10可以看出，CBFM索引方法的查詢耗時是BFM、MDBF、CBF等索引方法的2~3倍，這是由于在CBFM查詢過程中，需要針對刪減屬性進行查詢優(yōu)化，將原有查詢拆分為多次查詢，此性能損失可以通過算法并行化進行優(yōu)化解決，也是本文的下一步工作方向之一。

4.3 內存空間占用

為了驗證CBFM索引方法的內存高效性，本文在維度數(shù)={1,2,3,4}，單維期望元素數(shù)=100，期望誤判率=0.1場景下進行算法內存空間占用對比實驗。

圖11給出了CBFM理論內存占用、CBFM實際內存占用（CBFM在維度數(shù)等于3、4情況下刪減一個兩屬性組合）、BFM實際內存空間占用的對比測試結果。可以看出，CBFM內存空間占用理論值和實際值基本一致，這也驗證了理論分析的正確性。當維度數(shù)為1情況下，理論值與實際值的差距主要是由于程序內部變量所占內存空間導致。在實際內存空間占用對比方面，隨著維度數(shù)增大，BFM、CBFM方法占用內存均持續(xù)增加，但BFM內存空間增加趨勢更加明顯，特別是在維度數(shù)為4的場景下，BFM內存空間占用比CBFM方法高了2個數(shù)量級左右。

4.4 維度擴展性

圖12給出了在任意屬性組合查詢場景下，維度數(shù)與查詢效率之間的關系。實驗采用三維度數(shù)據集，單維度數(shù)組大小為16位，測試了維度數(shù)從2增長到8的過程。

CBFM算法查詢效率并沒有隨著維度數(shù)增加而線性增長，這更加有利于CBFM在高維數(shù)據集上的應用。同時，隨著插入數(shù)據集逐漸增大，特定維度查詢效率基本保持穩(wěn)定，這也驗證了CBFM算法查詢復雜度與插入數(shù)據集并無相關性。

5 結束語

多維元素成員查詢在分布式云存儲、網絡流量分析等系統(tǒng)中具有重要的應用意義，其核心挑戰(zhàn)在于多維索引結構的設計，支持全屬性及任意屬性組合成員查詢，同時具備較低的查詢誤判率和內存空間占用。為了提升多維元素成員查詢的靈活性和準確率，本文詳細分析了SBF[12]、MDBF[13]、CMDBF[14]、CBF[15]、BFM[16]等5種多維索引方法，并在此基礎上提出了一種新型索引結構CBFM(Cutted Bloom Filter Matrix)，該索引方法通過獨立屬性布魯姆過濾器笛卡爾乘積構建位矩陣，支持任意屬性組合的多維元素成員查詢，同時支持屬性組合按需刪減和屬性加權，提升內存空間利用率，降低查詢誤判率。本文詳細分析了CBFM索引結構的模型復雜度，并給出算法進行多維元素插入和成員查詢的工作流程。與此同時，本文從查詢誤判率、查詢效率、維度擴展性等多個角度進行了索引結構的驗證工作，實驗證明，相比于現(xiàn)有方法，CBFM具備相對更低的查詢誤判率，并具備較好的維度擴展性。

本文的下一步工作方向可以歸納為兩點。首先，目前主流的多維索引結構均假設所有屬性權重一致，本文雖然在多維元素成員查詢的屬性加權方面進行了初探，但是如何基于屬性差異化權重，實現(xiàn)屬性相應布魯姆過濾器的參數(shù)化調整策略仍是未來主要的工作方向；其次，如何分析多維查詢和數(shù)據集的相關性，并在已知數(shù)據集特征場景下進行算法適應性優(yōu)化也是本文一項重要的工作內容。

[1] LYNCH C. Big data: how do your data grow[J]. Nature, 2008, 455(7209): 28-29.

[2] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: a distributed storage system for structured data[J]. ACM Transactions on Computer Systems (TOCS), 2008, 26(2): 4.

[3] VORA M N. Hadoop-HBase for large-scale data[J]. IEEE Computer Science and Network Technology, 2011, (1): 601-605.

[4] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[5] THUSOO A, SARMA J S, JAIN N, et al. Hive: a warehousing solution over a map-reduce framework[J]. Proceedings of the VLDB Endowment, 2009, 2(2): 1626-1629.

[6] KORNACKER M, BEHM A, BITTORF V, et al. Impala: a modern, open-source SQL engine for Hadoop[C]. Conference on Innovative Data Systems Research (CIDR'15). c2015.

[7] TARKOMA S, ROTHENBERG C E, LAGERSPETZ E. Theory and practice of bloom filters for distributed systems[J]. Communications Surveys & Tutorials, IEEE, 2012, 14(1): 131-155.

[8] RODEH O, TEPERMAN A. zFS-a scalable distributed file system using object disks[C]//Mass Storage Systems and Technologies (MSST), c2003: 207-218.

[9] DEBNATH B, SENGUPTA S, LI J. FlashStore: high throughput persistent key-value store[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 1414-1425.

[10] ZHOU X, ZHANG X, WANG Y, et al. Efficient distributed multi-dimensional index for big data management[M]. Springer Berlin Heidelberg, 2013. 130-141.

[11] NISHIMURA S, DAS S, AGRAWAL D, et al. MD-HBase: a scalable multi-dimensional data infrastructure for location aware services[J]. IEEE Mobile Data Management (MDM), 2011, 1: 7-16.

[12] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426.

[13] GUO D, WU J, CHEN H, et al. Theory and network applications of dynamic bloom filters[C]//INFOCOM. c2006: 1-12.

[14] 謝鯤, 秦拯, 文吉剛, 等. 聯(lián)合多維布魯姆過濾器查詢算法[J]. 通信學報, 2008, 29(1): 56-64.

XIE K, QIN Z, WEN J G, et al.Combine multi-dimension Bloom filter for membership queries[J]. Journal on Communications，2008，29( 1) : 56-64.

[15] WANG Z, LUO T, XU G, et al. A new indexing technique for supporting by-attribute membership query of multidimensional data[M]. Springer Berlin Heidelberg, 2013. 266-277.

[16] WANG Z, LUO T, XU G, et al. The application of cartesian-join of bloom filters to supporting membership query of multidimensional data[C]//IEEE Big Data. c2014: 288-295.

[17] BRODER A, MITZENMACHER M. Network applications of bloom filters: a survey[J]. Internet Mathematics, 2004, 1(4): 485-509.

[18] CHENG X, LI H, WANG Y, et al. BF-matrix: a secondary index for the cloud storage[M]. Springer International Publishing, 2014. 384-396.

[19] CRAINICEANU A, LEMIRE D. Bloofi: multidimensional Bloom filters[J]. Information Systems, 2015, 54: 311-324.

CBFM：cutted Bloom filter matrix for multi-dimensional membership query

WANG Yong1, YUN Xiao-chun1,2, WANG Shu-peng1, WANG Xi1

(1.Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; 2. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China)

In order to improve the flexibility and accuracy of multi-dimensional membership query, a new indexing structure called CBFM(cutted Bloom filter matrix) was proposed. CBFM built the bit matrix by the Cartesian product of different bloom filters, each representing one attribute of primary data. In this way, the proposed matrix supported by-attribute membership query. Besides, the attribute combinations in the bit matrix could be reduced and weighted on demand to further enhance memory utilization rate. Theoretical analysis proves that CBFM utilizes memory more efficiently than BFM, the current state of art. Experiments also show that, on the scenario of memory size fixed, the false positive rate of CBFM is lower than that of all other indexing methods. Especially on the scenario of memory constrained, the false positive rate of CBFM can be 3 orders of magnitude lower than that of BFM(Bloom filter matrix) indexing method. CBFM is an accurate data structure for multi-dimensional membership query.

query algorithm, multi-dimensional membership query, Bloom filter, bit matrix

TP393

A

10.11959/j.issn.1000-436x.2016061

2015-08-16；

2015-12-04

國家自然科學基金資助項目（No.61271275, No.61501457, No.61202067, No.61303261）；國家高技術研究發(fā)展計劃(“863”計劃)基金資助項目（No.2012AA013001, No.2013AA013205, No.2013AA01A213）

The National Natural Science Foundation of China (No.61271275, No.61501457, No.61202067, No.61303261), The National High Technology Research and Development Program of China (863 Program) (No.2012AA013001, No.2013AA013205, No.2013AA01A213)

王勇（1985-），男，黑龍江雙鴨山人，中國科學院信息工程研究所博士生，主要研究方向為海量數(shù)據存儲、網絡安全。

云曉春（1971-），男，黑龍江哈爾濱人，博士，中國科學院信息工程研究所研究員、博士生導師，主要研究方向為網絡信息安全。

王樹鵬（1980-），男，山東濟南人，博士，中國科學院信息工程研究所副研究員，主要研究方向為海量數(shù)據存儲、網絡安全。

王曦（1985-），女，黑龍江哈爾濱人，中國科學院信息工程研究所助理研究員，主要研究方向為網絡安全。