嚴(yán)華云,關(guān)佶紅
(1.湖州師范學(xué)院信息與工程學(xué)院 湖州 313000;2.同濟(jì)大學(xué)電子與信息工程學(xué)院 上海 201804)
在計(jì)算機(jī)應(yīng)用領(lǐng)域,信息的表示和查詢是核心問題,這兩個(gè)問題常常是相關(guān)的。其中,表示意味著根據(jù)一定的規(guī)則組織信息,查詢則意味著判斷一個(gè)給定屬性值的元素是否屬于某一集合。
Bloom filter[1]是一種節(jié)省空間、高效率的數(shù)據(jù)表示和查詢結(jié)構(gòu)。它利用位數(shù)組很簡潔地表示一個(gè)集合,并能以很高的概率判斷一個(gè)元素是否屬于這個(gè)集合。因此,這種數(shù)據(jù)結(jié)構(gòu)適合應(yīng)用在能容忍低錯(cuò)誤率的場合。
Burton H.Bloom于1970年提出Bloom filter用以解決某(些)元素是否為集合中元素的判斷問題。它突破了傳統(tǒng)哈希函數(shù)的映射和存儲(chǔ)元素的方式,通過一定的錯(cuò)誤率換取了空間的節(jié)省和查詢的高效。在20世紀(jì)70年代,其應(yīng)用價(jià)值并沒有體現(xiàn)出來。80年代,隨著PC應(yīng)用的推廣,Bloom filter的應(yīng)用開始推廣,如高效地解決拼寫檢查問題[2],解決多處理器計(jì)算機(jī)中數(shù)據(jù)庫的連接問題[3]。網(wǎng)絡(luò)時(shí)代的到來使得Bloom filter具有越來越多的應(yīng)用,如應(yīng)用到分布式數(shù)據(jù)庫中進(jìn)行查詢[4,5],應(yīng)用到網(wǎng)絡(luò)中取代ICP以進(jìn)行高速緩存查詢[6],應(yīng)用到P2P中進(jìn)行高效的聯(lián)合查詢[7,8]等。肖明忠、Broder、謝鯤等分別于2003年、2004年、2007年寫了Bloom filter的綜述性文獻(xiàn)[9~11]。近幾年,Bloom filter及其應(yīng)用又取得了新的進(jìn)展,本文對(duì)Bloom filter在通信領(lǐng)域的研究進(jìn)行歸納和展望,并介紹了Bloom filter的典型應(yīng)用。
標(biāo)準(zhǔn)Bloom filter的工作原理如圖1所示。為了表達(dá)S={x1,x2,…,xn}這樣一個(gè)有n個(gè)元素的集合,Bloom filter使用k個(gè)相互獨(dú)立的哈希函數(shù)(hash function),它們分別將集合中的每個(gè)元素映射到位數(shù)組BFV的k個(gè)位中(BFV共有m位)。對(duì)任意一個(gè)元素x,第i個(gè)哈希函數(shù)映射的位置 hi(x)就會(huì)被置為 1(1≤i≤k),如果一個(gè)位置已經(jīng)為 1,那么隨后映射到該位置時(shí)其值將不變。
當(dāng)查詢?cè)貁i時(shí),用Bloom filter中的k個(gè)哈希函數(shù)映射到BFV中,如果每一個(gè)哈希函數(shù)映射到的位都為1,則認(rèn)為zi屬于S,否則 zi不屬于S。
與經(jīng)典的哈希函數(shù)相比,Bloom filter最大的優(yōu)勢是它的空間效率。另外,由于Bloom filter不用處理碰撞,無論集合中元素有多少,也無論多少集合元素已經(jīng)加入到了位向量中,Bloom filter在增加或查找集合元素時(shí)所用的時(shí)間都為哈希函數(shù)的計(jì)算時(shí)間。由于Bloom filter對(duì)集合中的元素進(jìn)行了編碼,因此想從Bloom filter的位向量中恢復(fù)集合元素并不容易,如果不想讓別人直接看到集合元素,這樣的編碼處理相當(dāng)于一種加密,從而有利于保護(hù)隱私。
Bloom filter的這些優(yōu)點(diǎn)是有一定代價(jià)的:在判斷某一個(gè)元素zi是否屬于集合S時(shí),有可能會(huì)把不屬于S中的元素誤認(rèn)為屬于S,這種情況稱為“假陽性”的“錯(cuò)誤率”(false positive),這個(gè)錯(cuò)誤率可以通過概率的方法計(jì)算出來。因此,Bloom filter不適合那些“零錯(cuò)誤”的應(yīng)用場合。
在標(biāo)準(zhǔn)的Bloom filter中,對(duì)于使用k個(gè)哈希函數(shù),向m位長的Bloom filter中裝入n個(gè)元素后,位向量中某一位仍然為0的概率p為:
則錯(cuò)誤率fp為:
在式(2)中,令g=-(m/n)ln(p)ln(1-p),根據(jù)對(duì)稱性法則可知,當(dāng)p=1/2,g取到最小值,則fp取到最小值。
錯(cuò)誤率fp最小的條件為:
由此可見,標(biāo)準(zhǔn)Bloom filter中參數(shù)m、n的比值是已知的,為了保證錯(cuò)誤率最小,則要求k=(m/n)ln2,此時(shí)BFV中某一位為零的概率為1/2(即p=1/2)。將式(3)代入式(2)有:
由式(3)和式(4)可知,當(dāng)m和n的比值越大則要求哈希函數(shù)的個(gè)數(shù)k越大,并且其錯(cuò)誤率越小。
自從Bloom filter在通信領(lǐng)域得到廣泛應(yīng)用后,研究人員在不同的應(yīng)用背景下對(duì)Bloom filter進(jìn)行了一些改進(jìn),下面對(duì)Bloom filter的一些典型變體進(jìn)行介紹。
由于在Bloom filter中不可以刪除元素,參考文獻(xiàn)[6]在對(duì)網(wǎng)頁進(jìn)行緩存時(shí)(集合中元素不重合),為了更新并淘汰過時(shí)的網(wǎng)頁,設(shè)計(jì)了一種稱為Couting Bloom filter(計(jì)數(shù)型CBF)的變體,其具體辦法為:將圖1中向量BFV的每一位擴(kuò)展成幾位(詳細(xì)如圖2所示的CBFV,文中稱擴(kuò)展成的這幾位為一個(gè)計(jì)數(shù)器 (counter))。
經(jīng)擴(kuò)展后,當(dāng)某一個(gè)元素要插入集合S時(shí),分別用k個(gè)哈希函數(shù)映射到CBFV的k位計(jì)數(shù)器,將這些計(jì)數(shù)器增加1;當(dāng)某一個(gè)元素要從集合S刪除時(shí),分別用k個(gè)哈希函數(shù)映射到CBFV上的k個(gè)計(jì)數(shù)器,并將這些計(jì)數(shù)器減少1個(gè)。通過擴(kuò)展BFV的位成為CBFV計(jì)數(shù)器后的CBF,就能夠處理元素刪除的操作。對(duì)于網(wǎng)頁緩存這類不重復(fù)元素問題,當(dāng)CBF中計(jì)數(shù)器用4位時(shí),經(jīng)過相應(yīng)推導(dǎo),出現(xiàn)溢出的概率為:
式(5)表示的是計(jì)數(shù)器中最大值大于等于16出現(xiàn)的概率,其中m是CBFV的長度。即使某一位計(jì)數(shù)器出現(xiàn)溢出,也不會(huì)導(dǎo)致馬上出現(xiàn)錯(cuò)誤,而是刪除元素直到該位計(jì)數(shù)器為零后才會(huì)出現(xiàn)所謂的 “假陰性”的 “錯(cuò)誤率”(false negative),即把屬于該集合的元素誤認(rèn)為不屬于該集合的錯(cuò)誤,因此出現(xiàn)“假陰性”的“錯(cuò)誤率”的概率為式(5)的2倍。因此,將CBF的計(jì)數(shù)器設(shè)計(jì)成4位是合理的。
針對(duì)CBF可能溢出的問題,有一種解決方法叫做d-Left Counting Bloom filter(dlCBF)[12]。
dlCBF通過引入一種叫做d-Left hash的更均衡的哈希函數(shù)來降低CBF向量中counter的位數(shù)。在添加一個(gè)key時(shí),先對(duì)其作一次hash,得到d個(gè)存儲(chǔ)位置和一個(gè)fingerprint,然后判斷d個(gè)位置中的負(fù)載情況,并在負(fù)載最輕的幾個(gè)位置中選擇最左邊的插入。如果選擇的位置已經(jīng)存儲(chǔ)了相同的fingerprint,就把那個(gè)cell的counter加1。在刪除一個(gè)key時(shí),同樣地作一次hash,然后在d個(gè)存儲(chǔ)位置查找相應(yīng)的fingerprint,如果找到就將這個(gè)cell置空或者將相應(yīng)的counter減1。
在集合中刪除元素時(shí)可能會(huì)出現(xiàn):不同的兩個(gè)元素的hash值(fingerprint)相同,從而刪除元素時(shí)不好判斷將哪一個(gè)counter減1。為了解決這個(gè)問題,該文引入隨機(jī)置換避免了位置重合,從而使問題得以解決。
為了節(jié)省CBF的存儲(chǔ)空間,提出了MultiLayer compressed counting bloom filter[13],該 Bloom filter也支持集合中刪除元素的操作。
當(dāng)應(yīng)用中需要統(tǒng)計(jì)元素出現(xiàn)的頻次(即重復(fù)元素問題)時(shí),由于CBF的計(jì)數(shù)器采用固定長度的位數(shù),會(huì)產(chǎn)生溢出(overflow)的問題。為了解決這種溢出,相關(guān)文獻(xiàn)提出了兩種方法:一種是參考文獻(xiàn)[14]提出的Spectral Bloom filter(SBF),由于SBF中要建立索引,查詢起來比較費(fèi)時(shí);為進(jìn)一步解決SBF訪問速度的問題,參考文獻(xiàn)[15]提出了另一種數(shù)據(jù)結(jié)構(gòu)Dynamic count filter(DCF)。對(duì)于動(dòng)態(tài)計(jì)數(shù)型的Bloom filter,下面選擇DCF進(jìn)行介紹。
DCF的數(shù)據(jù)結(jié)構(gòu)如圖2所示,它由兩部分組成,一部分是前面提到的CBFV向量,其位長度x由集合中數(shù)據(jù)元素的總個(gè)數(shù)M和集合中不同元素的總個(gè)數(shù)n的比值取2為底的對(duì)數(shù)確定;另一部分是為了處理CBFV溢出而設(shè)計(jì)的OFV向量,其位數(shù)y值是動(dòng)態(tài)變化的(DCF的動(dòng)態(tài)體現(xiàn)在這里),其值由集合中元素出現(xiàn)的最高頻次所決定。DCF中計(jì)數(shù)器的值Value是由OFV和CBFV中相同下標(biāo)位的二進(jìn)制數(shù)連接而成。當(dāng)需要查詢某元素在DCF的出現(xiàn)頻次時(shí),就用DCF的k個(gè)哈希函數(shù)映射到DCF數(shù)據(jù)結(jié)構(gòu)上,其中的最小值(value)就被認(rèn)為是其頻次(最小值不是頻次的情況是k個(gè)位置同時(shí)出現(xiàn)了碰撞,這個(gè)概率和誤判率的概率相同)。
前面所介紹的Bloom filter應(yīng)用有一個(gè)共同點(diǎn),即事先能夠確定集合S中的元素個(gè)數(shù)m。事實(shí)上,很多應(yīng)用在事先并不清楚要處理多大的數(shù)據(jù)集;或者要處理很大的一個(gè)數(shù)據(jù)集,但數(shù)據(jù)元素的加入是緩慢的。參考文獻(xiàn)[16]稱這種問題為增長問題,這種情況在P2P環(huán)境中經(jīng)常出現(xiàn)。為了處理這類問題,出現(xiàn)了一類可以拉伸位數(shù)組 (BF)個(gè)數(shù)的Bloom filter[16~19]。下面介紹 Dynamic Bloom filter(DBF,動(dòng) 態(tài)Bloom filter)。
DBF的辦法是先用一個(gè)能處理較少元素的Bloom filter來處理,當(dāng)此Bloom filter達(dá)到處理元素的極限時(shí),再生成一個(gè)和初始Bloom filter長度相同的Bloom filter,如此這般。新元素加入時(shí)映射到最新生成的Bloom filter中,查詢時(shí)在幾個(gè)子Bloom filter都同時(shí)進(jìn)行查詢,只要映射到DBF中的一個(gè)子Bloom filter的k個(gè)位置的值都為1,則認(rèn)為該元素為集合中的元素。
由于這種方法可以看成由多個(gè)Bloom filter向量組成的一個(gè)矩陣,由應(yīng)用需要取其中一個(gè)或多個(gè)Bloom filter進(jìn)行使用,因此參考文獻(xiàn)[16]稱之為拆分型Bloom filter。
在標(biāo)準(zhǔn)Bloom filter中,已知參數(shù)m、n的比值,為使錯(cuò)誤率最小,則要求k=(m/n)ln2(具體推導(dǎo)見參考文獻(xiàn)[10])。參考文獻(xiàn)[20]考慮在網(wǎng)絡(luò)中傳播消息時(shí)要進(jìn)行壓縮,這時(shí)Bloom filter不再是僅由m、n、k這3個(gè)參數(shù)決定錯(cuò)誤率,應(yīng)該加上z參數(shù)(表示Bloom filter的位向量被壓縮后的長度),這4個(gè)參數(shù)一起決定了錯(cuò)誤率,這就是所謂的Compressed Bloom filter(壓縮型BF)。由于壓縮編碼時(shí)要服從香農(nóng)編碼原理,即壓縮編碼后的最大壓縮比不小于信息熵H(P),即有最小的z=m H(P),引入z后的分析和標(biāo)準(zhǔn)的Bloom filter中的分析相同,即將z取代m代入錯(cuò)誤率的表達(dá)式中。經(jīng)過一定的變換分析得出:當(dāng)p=1/2時(shí),其錯(cuò)誤率最大(此時(shí)的熵為1,即根本得不到壓縮,此時(shí)和標(biāo)準(zhǔn)BF中的正好相反);當(dāng)p越接近0時(shí)(k趨于無窮,此種情況不符合實(shí)際應(yīng)用)和p越接近1時(shí) (k趨于0,實(shí)際應(yīng)用中1≤k≤(m/n)ln2),其錯(cuò)誤率越小,其詳細(xì)推導(dǎo)見參考文獻(xiàn)[20]。為了對(duì)壓縮型BF有更深的了解,表1列出了各個(gè)參數(shù)和錯(cuò)誤率間的關(guān)系,其中z/n是固定的。
表1 壓縮型Bloom filter中各參數(shù)和錯(cuò)誤率的關(guān)系
表1中第一列數(shù)據(jù)(加粗的數(shù)據(jù))是沒有壓縮的情況,此時(shí)需要k的個(gè)數(shù)最多,且錯(cuò)誤率最高。隨著壓縮比越大,則需要k的個(gè)數(shù)越少,錯(cuò)誤率也更低,這說明壓縮能夠降低錯(cuò)誤率。
表2列出了幾種經(jīng)典Bloom filter的性能比較。從該表可以看出:所有的Bloom filter都具有基本的功能,即進(jìn)行集合元素的表示和查詢;支持元素頻次查詢操作的Bloom filter一定支持刪除元素操作。
表2 幾種經(jīng)典Bloom filter的性能比較
Bloom filter的應(yīng)用包括:它表示一種壓縮數(shù)據(jù)集合,可以替代原始的數(shù)據(jù)集合,完成元素是否在集合的查詢判斷,如數(shù)據(jù)庫操作、字典查詢和文件操作[2,3,21~24]方面;Bloom filter也廣泛應(yīng)用到網(wǎng)絡(luò)領(lǐng)域,包括P2P網(wǎng)絡(luò)[7,8,25,26]、資源路由[27]、數(shù)據(jù)幀路由標(biāo)簽[28]、網(wǎng)絡(luò)測量管理[29~32]、網(wǎng)絡(luò)入侵檢測[33]、傳感器網(wǎng)絡(luò)數(shù)據(jù)過濾和路由[34]等;第三類是元素表示的保密性。因此,凡是有上述3類要求的,并且能容忍一定錯(cuò)誤率的應(yīng)用都可以將Bloom filter派上用場。Broder和Mitzenmacher在2004年的綜述論文[10]中預(yù)言:當(dāng)前Bloom filter在網(wǎng)絡(luò)上的應(yīng)用還十分有限,隨著Bloom filter被越來越多的研究人員認(rèn)識(shí)和重視,它將在現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)和一些新的學(xué)術(shù)領(lǐng)域得到更為廣泛的應(yīng)用。確實(shí),Bloom filter這幾年的應(yīng)用研究正在而且必將繼續(xù)印證該論斷。
圖3為Bloom filter在分布式系統(tǒng)中的應(yīng)用例子。當(dāng)客戶向服務(wù)器A提出請(qǐng)求時(shí):A首先檢查本身的緩存和其他近鄰Proxy(如B)的緩存,這些緩存的目錄摘要用Bloom filter表示,如果A及其近鄰Proxy的緩存目錄摘要里有文檔信息,則向相應(yīng)的近鄰Proxy請(qǐng)求以獲取文件,如果沒有,就直接向上級(jí)服務(wù)器發(fā)送請(qǐng)求。
[35]是Bloom filter源代碼的下載地址,該源碼用Java語言實(shí)現(xiàn),該源碼由Indiana大學(xué)的Liu Hongbin和Jerzak提供,它實(shí)現(xiàn)了兩種Bloom filter:一個(gè)是標(biāo)準(zhǔn)的Bloom filter,它用BitSet表示;另一個(gè)是支持刪除元素的Counting Bloom filter,它用一個(gè)數(shù)組表示。HashFactory(m,k)是生成BF的接口,其中需要給出兩個(gè)參數(shù)m和k(即BF的長度和哈希函數(shù)的個(gè)數(shù)),其中可供選擇的哈希函數(shù)個(gè)數(shù)k共有10個(gè)(即k不能超過10,當(dāng)然自己可以根據(jù)需要擴(kuò)展)。
使用Bloom filter可達(dá)到兩方面的性能:壓縮數(shù)據(jù)和高查詢效率 (時(shí)間為計(jì)算哈希函數(shù)的時(shí)間)。只要在具體應(yīng)用中需要Bloom filter的任何性能,并能夠容忍較小的錯(cuò)誤率,都可以引入Bloom filter。
Bloom filter雖然根據(jù)不同應(yīng)用需求具有了很多變體,但是其仍有很多應(yīng)用需要改進(jìn),主要有以下3方面。
(1)網(wǎng)絡(luò)傳輸中壓縮型Bloom filter的實(shí)現(xiàn)
由于Bloom filter及其變體被廣泛應(yīng)用于分布式數(shù)據(jù)庫、Proxy的Cache、對(duì)等網(wǎng)等網(wǎng)絡(luò)環(huán)境中,在網(wǎng)絡(luò)傳輸中如何進(jìn)行壓縮是一個(gè)問題。參考文獻(xiàn) [20]從理論上提出了CBF,但文中沒有給出具體的實(shí)現(xiàn)。另外,在DCF的推理中用到了極限熵進(jìn)行壓縮編碼,我們知道一般編碼是很難達(dá)到極限熵的,對(duì)特定數(shù)據(jù)集能夠達(dá)到極限熵編碼,對(duì)其他數(shù)據(jù)未必就能達(dá)到極限熵編碼,例如常見的哈夫曼編碼就是一個(gè)例子。因此,Bloom filter網(wǎng)絡(luò)傳輸問題的壓縮編碼算法還有待研究。
(2)Bloom filter結(jié)構(gòu)在海量數(shù)據(jù)問題中的擴(kuò)展
在對(duì)等網(wǎng)、信息檢索領(lǐng)域中,所涉及的數(shù)據(jù)量非常大,并且沒辦法估計(jì)數(shù)據(jù)量的大小,或者考慮到數(shù)據(jù)量是漸增和動(dòng)態(tài)變化的,沒必要一開始就建立一個(gè)很大的Bloom filter,在數(shù)據(jù)量漸增和動(dòng)態(tài)變化的過程中需要能夠建立一種能夠動(dòng)態(tài)伸縮的Bloom filter。
(3)并行 Bloom filter的需求
在網(wǎng)絡(luò)Cache和一些信息安全領(lǐng)域用到Bloom filter時(shí),需要Bloom filter具有快捷的速度。這種情況下,需要將Bloom filter做到硬件中,并且最好能夠提供并行計(jì)算的功能,目前Bloom filter的變體基本上都不支持并行計(jì)算的功能。Bloom filter的并行性需求有待我們?nèi)パ芯俊?/p>
總之,自從Burton Bloom在1970年提出Bloom filter之后,Bloom filter就被廣泛用于拼寫檢查和數(shù)據(jù)庫系統(tǒng)中。隨著網(wǎng)絡(luò)的普及和發(fā)展,Bloom filter的研究和應(yīng)用迅猛發(fā)展,新的Bloom filter變種和新的應(yīng)用不斷出現(xiàn)??梢灶A(yù)見,隨著互聯(lián)網(wǎng)的不斷發(fā)展,Bloom filter的新變種和應(yīng)用將會(huì)繼續(xù)出現(xiàn)。
參考文獻(xiàn)
1 Bloom B H.Space/time trade-offs in hash coding with allowable errors.Communications of the ACM,1970,13(7):422~426
2 Mcilroy M D.Development of a spelling list.IEEE Transactions on Communications,1982,30(1):91~99
3 Valdurez P,Gardarin G.Join and semijoin algorithms for a multiprocessor database machine.ACM Transactions on Database Systems,1984,9(1):133~161
4 MackettL F,Lohman G M.Roptimizer validation and performance evaluation for distributed queries.In:Proc of the VLDB,Kyoto,Japan,August 1986
5 Mullin J K.Optimal semijoins for distributed database systems.IEEE Transactions on Software Engineering,1990,16(5):558~560
6 Fan L,Cao P,Almeida J,et al.Summary cache:a scalable wide-area Web cache sharing protocol.ACM Transactions on Networking,2000,8(3):281~293
7 Reynolds P,Vahdat A.Efficient peer-to-peer keyword searching.In:Proc of Middleware,Riode Janeiro,Brazil,June 2003
8 Chen H H,Jin H,Wang J L,et al.Efficient multi-keyword search over P2P web.In:Proc of the WWW,Beijing,China,April 2008
9 肖明忠,代亞非.Bloom Filter及其應(yīng)用綜述.計(jì)算機(jī)科學(xué),2004,31(4):180~183
10 Broder A,Mitzenmacher M.Network applications of bloom filters:a survey.Internet Mathematics,2005,1(4):485~509
11 謝鯤,文吉?jiǎng)?張大方等.布魯姆過濾器查詢算法.軟件學(xué)報(bào),2009,20(1):96~108
12 Bonomi F,Mitzenmacher M,Panigrahy R,et al.An improved construction for counting bloom filters.In:Lecture Notes in Computer Science,Zurich,Switzerland,September 2006
13 Ficara D,Giordano S,Procissi G.MultiLayer compressed counting bloom filters.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008
14 Saar C,Yossi M.Spectral bloom filters.In:Proc of the SIGMOD,San Diego,USA,June 2003
15 Aguilar-Saborit J,Trancoso P,Muntes-Mulero V.Dynamic count filters.In:Proc of the SIGMOD,Chicago,USA,June 2006
16 肖明忠,代亞非,李曉明.拆分型Bloom Filter.電子學(xué)報(bào),2004,32(2):241~245
17 Guo D,Wu J,Chen H,et al.Theory and network applications of dynamic bloom filters.In:Proc of the Infocom,Barcelona,Spain,April 2006
18 Almeida P S,Baquero C,Preguica N.Scalable bloom filters.Information Processing Letters,2007,101(6):255~261
19 Hao F,Kodialam M,Lakshman T V.Incremental bloom filters.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008
20 Mitzenmacher M.Compressed bloom filters.ACM Transactions on Networking,2002,10(5):604~612
21 Mullin J K.Optimal semijoins for distributed database systems.IEEE Transactions on Software Engineering,1990,16(5):558~560
22 Udi M,Sun W.An algorithm for approximate membership checking with application to password security.Information Processing Letters,1994,50(4):191~197
23 Gremillion L L.Designing a bloom filter for differential file access.Communications of the ACM,1982,25(9):600~604
24 James K M.A second look at bloom filters.Communications of the ACM,1983,26(8):570~571
25 Ahmed R,Boutaba R.Plexus:a scalable peer-to-peer protocol enabling efficient subset search. ACM Transactions on Networking,2009,17(1):130~143
26 張一鳴,盧錫城,鄭倩冰等.一種面向大規(guī)模P2P系統(tǒng)的快速搜索算法.軟件學(xué)報(bào),2008,19(6):1473~1480
27 Yu H,Mahapatra R N.A memory-efficienthashing by multi-predicate bloom filters for packet classification.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008
28 Kumar A,Xu J,Wang J,Spatschek O,et al.SpaceScode bloom filter for efficient persflow traffic measurement.In:Proc of IEEE Infocom,Hongkong,March 2004
29 葉明江,崔勇,徐恪等.基于有狀態(tài)Bloom filter引擎的高速分組檢測.軟件學(xué)報(bào),2007,18(1):117~126
30 Yu H,Mahapatra R N.A memory-efficienthashing by multipredicate bloom filters for packet classification.In:Proc of Infocom,Phoenix,AZ,USA,April 2008
31 Sarang D, Haoyu S, Jonathan T, et al. Fast packet classification using bloom filters.In:Proc of the 2006 ACM/IEEE Symp Architecture for Networking and Communications Systems,2006
32 HeeyeolY,Mahapatra R.A memory-efficienthashing by multi-predicate bloom filters for packet classification.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008
33 Locasto M E,Parekh J J,Keromytis A D,et al.Towards collaborative security and P2P intrusion detection.In:Proc of SMC 2005,NY,USA,June 2005
34 Hebden P,Pearce A R.Data-centric routing using bloom filters in wireless sensor networks.In:Proc of ICISIP 2006,Bangalore,India,December 2006
35 Bloomfilter,http://wwwse.inf.tu-dresden.de/xsiena/bloom_filter