王勇，云曉春,2，王樹(shù)鵬，王曦

?

CBFM：支持屬性刪減的布魯姆過(guò)濾器矩陣多維元素查詢(xún)算法

王勇1，云曉春1,2，王樹(shù)鵬1，王曦1

（1. 中國(guó)科學(xué)院信息工程研究所北京 100093；2. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心北京 100029）

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

查詢(xún)算法；多維元素成員查詢(xún)；布魯姆過(guò)濾器；位矩陣

1 引言

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

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

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

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

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

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

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

2 相關(guān)研究工作

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

2.1 布魯姆過(guò)濾器

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

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

2.2 布魯姆過(guò)濾器多維擴(kuò)展

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

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

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

2.3 其他相關(guān)研究工作

除布魯姆過(guò)濾器及其多維擴(kuò)展外，多維元素成員查詢(xún)典型解決方案包括表索引[8,9]、樹(shù)索引[10,11]及混合索引[18,19]結(jié)構(gòu)等。

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

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

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

3 CBFM設(shè)計(jì)

3.1 形式化定義

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

基于應(yīng)用場(chǎng)景差異，多維元素成員查詢(xún)支持2種查詢(xún)模式。針對(duì)全屬性查詢(xún)模式，查詢(xún)?cè)貎?nèi)容；任意屬性組合查詢(xún)模式，查詢(xún)?cè)貎?nèi)容。多維元素成員查詢(xún)返回true/ false的結(jié)果，返回true；返回false。

3.2 CBFM算法

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

表1 CBFM運(yùn)行參數(shù)

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

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

CBFM索引結(jié)構(gòu)在默認(rèn)情況下，所有屬性權(quán)重相等，位向量大小保持一致。為了更好地支持多維元素成員查詢(xún)場(chǎng)景下屬性權(quán)重的差異性，CBFM可以擴(kuò)展為加權(quán)模型（WCBFM-Weighted CBFM），即可以針對(duì)重要屬性或?qū)傩越M合，分配相對(duì)較大的內(nèi)存空間，進(jìn)一步降低查詢(xún)誤判率。

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

算法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[][];} //針對(duì)每個(gè)屬性計(jì)算k次散列} //end forfor each DC of (2d?1) combinations { for each hash value hashV in hashPerField { //調(diào)用calculateIndex計(jì)算實(shí)際索引下標(biāo) invoke calculateIndex(DC, hashV, ResultArray);}} //end for//采用實(shí)際索引下標(biāo)對(duì)位數(shù)組進(jìn)行置1處理for each idx of ResultArray { set bit of ResultArray [idx] to 1} //end forend elementInsert

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

算法2 elementSearch(Object Element)輸入:待查詢(xún)的多維元素A=(a1,a2,…,ad), 其對(duì)應(yīng)維度組合SDC，非必選字段值為null輸出:元素是否存在beginassign 0 to ResultArray;for each field ax in A { for each hashFunction hashx in HashSet { record hashx(ax) to hashPerField[][];} //針對(duì)每個(gè)屬性計(jì)算k次散列} //end forfor each EDC(does not match any dimension combinations to cut off) of SDC { for each hash value hashV in hashPerField { //調(diào)用calculateIndex計(jì)算實(shí)際索引下標(biāo) 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 模型復(fù)雜度分析

根據(jù)布魯姆過(guò)濾器基本原理得知，假設(shè)散列取值服從均勻分布，當(dāng)集合中所有元素都映射完畢后，查詢(xún)誤判率為[17]

假設(shè)期望誤判率和期望元素?cái)?shù)已經(jīng)固定，在此基礎(chǔ)上計(jì)算散列函數(shù)個(gè)數(shù)和位向量的最優(yōu)解為

(2)

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

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

算法3 calculateIndex(Object DC, Object hashV, Object ResultArray)輸入:插入元素A=(a1,a2,…,ad)的一種維度組合; 使用某散列函數(shù)計(jì)算出每個(gè)字段的散列值數(shù)組; 需要置位的位索引數(shù)組輸出:VOIDbeginif DC match some dimension combinations to cut off { end calculateIndex; //維度組合與刪減組合一致}assign 0 to currentBitIndex;//由高位至低位遍歷DC中的每個(gè)維度信息for each dimension ax in DC(from high to low) { //將ax按照特殊位和非特殊位獨(dú)立處理 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ù)值示例，它們分別對(duì)比了BFM和CBFM算法，隨著期望誤判率的變化，期望元素?cái)?shù)和期望內(nèi)存空間占用的變化趨勢(shì)。在表2中，預(yù)設(shè)總可用內(nèi)存大小為1 MB，期望誤判率從10?1變化到10?5，在三維數(shù)據(jù)集場(chǎng)景下，CBFM刪減2個(gè)兩屬性組合(0x5代表刪減維度1、3；0x3代表刪減維度1、2)，CBFM期望元素個(gè)數(shù)始終是BFM的14倍以上，這也預(yù)示著CBFM在查詢(xún)誤判率上的優(yōu)勢(shì)。在表3中，期望插入元素?cái)?shù)=1 000，CBFM內(nèi)存占用比BFM低3個(gè)數(shù)量級(jí)以上，間接反映了CBFM索引方法具備相對(duì)較高的內(nèi)存空間利用率。

表2 期望元素?cái)?shù)量對(duì)比(M=1 MB)

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

4 仿真實(shí)驗(yàn)

本節(jié)通過(guò)仿真實(shí)驗(yàn)測(cè)試CBFM索引結(jié)構(gòu)在不同屬性組合場(chǎng)景下的查詢(xún)誤判率、查詢(xún)效率、內(nèi)存空間占用等核心指標(biāo)，并與SBF、MDBF、CMDBF、BFM、CBF等索引算法進(jìn)行比較。

4.1 查詢(xún)誤判率

本文分別在全屬性查詢(xún)、兩屬性查詢(xún)場(chǎng)景下，對(duì)比了SBF[12]、MDBF[13]、CMDBF[14]、CBF[15]、BFM[16]、CBFM這6種索引結(jié)構(gòu)，其中，CBFM索引結(jié)構(gòu)刪減了一個(gè)兩屬性組合。

實(shí)驗(yàn)1 構(gòu)造數(shù)據(jù)集驗(yàn)證查詢(xún)誤判率

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

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

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

實(shí)驗(yàn)2 根據(jù)實(shí)際數(shù)據(jù)集驗(yàn)證查詢(xún)誤判率

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

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

實(shí)驗(yàn)3 屬性加權(quán)查詢(xún)誤判率測(cè)試

為了驗(yàn)證屬性加權(quán)對(duì)于查詢(xún)誤判率的影響，本文針對(duì)三維度數(shù)據(jù)集下，在實(shí)驗(yàn)1基礎(chǔ)上提升2個(gè)屬性存儲(chǔ)權(quán)重，降低第3個(gè)屬性存儲(chǔ)權(quán)重，總存儲(chǔ)空間不變，得到的測(cè)試結(jié)果如圖9所示。

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

4.2 查詢(xún)效率

在進(jìn)行查詢(xún)誤判率實(shí)驗(yàn)的同時(shí)，本文記錄了查詢(xún)過(guò)程中的耗時(shí)情況，具體實(shí)驗(yàn)結(jié)果如圖10所示。

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

4.3 內(nèi)存空間占用

為了驗(yàn)證CBFM索引方法的內(nèi)存高效性，本文在維度數(shù)={1,2,3,4}，單維期望元素?cái)?shù)=100，期望誤判率=0.1場(chǎng)景下進(jìn)行算法內(nèi)存空間占用對(duì)比實(shí)驗(yàn)。

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

4.4 維度擴(kuò)展性

圖12給出了在任意屬性組合查詢(xún)場(chǎng)景下，維度數(shù)與查詢(xún)效率之間的關(guān)系。實(shí)驗(yàn)采用三維度數(shù)據(jù)集，單維度數(shù)組大小為16位，測(cè)試了維度數(shù)從2增長(zhǎng)到8的過(guò)程。

CBFM算法查詢(xún)效率并沒(méi)有隨著維度數(shù)增加而線(xiàn)性增長(zhǎng)，這更加有利于CBFM在高維數(shù)據(jù)集上的應(yīng)用。同時(shí)，隨著插入數(shù)據(jù)集逐漸增大，特定維度查詢(xún)效率基本保持穩(wěn)定，這也驗(yàn)證了CBFM算法查詢(xún)復(fù)雜度與插入數(shù)據(jù)集并無(wú)相關(guān)性。

5 結(jié)束語(yǔ)

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

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

[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] 謝鯤, 秦拯, 文吉?jiǎng)? 等. 聯(lián)合多維布魯姆過(guò)濾器查詢(xún)算法[J]. 通信學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61271275, No.61501457, No.61202067, No.61303261）；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)基金資助項(xiàng)目（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-），男，黑龍江雙鴨山人，中國(guó)科學(xué)院信息工程研究所博士生，主要研究方向?yàn)楹Ａ繑?shù)據(jù)存儲(chǔ)、網(wǎng)絡(luò)安全。

云曉春（1971-），男，黑龍江哈爾濱人，博士，中國(guó)科學(xué)院信息工程研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全。

王樹(shù)鵬（1980-），男，山東濟(jì)南人，博士，中國(guó)科學(xué)院信息工程研究所副研究員，主要研究方向?yàn)楹Ａ繑?shù)據(jù)存儲(chǔ)、網(wǎng)絡(luò)安全。

王曦（1985-），女，黑龍江哈爾濱人，中國(guó)科學(xué)院信息工程研究所助理研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)安全。