[發(fā)明專利]一種索引拆分布魯姆過濾器及其插入、刪除和查詢方法

無效

• 申請?zhí)枺?/td>: 200910138248.3
• 申請日: 2009-05-08
• 公開（公告）號: CN101577721A
• 公開（公告）日: 2009-11-11
• 發(fā)明（設(shè)計）人: 張大方;黃昆
• 申請（專利權(quán)）人: 湖南大學(xué)
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L9/36
• 代理公司: 長沙正奇專利事務(wù)所有限責(zé)任公司
• 代理人: 馬 強(qiáng)

1、一種索引拆分布魯姆過濾器，其特征是由多組片上并行計數(shù)布魯姆過濾器(CBF)和一個片外特征規(guī)則集構(gòu)成，且多組片上并行CBF產(chǎn)生與數(shù)據(jù)包內(nèi)容匹配的候選特征規(guī)則的片外索引值；所述片上并行CBF是指：將一組n條特征規(guī)則的索引值被拆分成組，每組包含索引值的b位比特；每組b位比特將特征規(guī)則集劃分成2^b個子集，該每個子集采用片上計數(shù)布魯姆過濾器CBF表示，從而為每組構(gòu)建2^b個片上并行CBF；當(dāng)查詢數(shù)據(jù)包內(nèi)容y時，檢查y是否在所有B×2^b個片上并行CBF中，每組片上并行CBF產(chǎn)生一個b位比特值，且將B個b位比特值合成候選特征規(guī)則的片外索引值。

2、一種權(quán)利要求1所述索引拆分布魯姆過濾器的特征規(guī)則刪除方法，其特征是采用一個刪除位圖記錄片外特征規(guī)則的狀態(tài)，即0表示未刪除狀態(tài)，1表示刪除狀態(tài)；當(dāng)刪除特征規(guī)則x時，在刪除位圖中設(shè)置x對應(yīng)的比特值為1，從每組片上并行CBF中刪除x，并從片外特征規(guī)則集中刪除x，且其他特征規(guī)則的片外索引值保持不變。

3、一種權(quán)利要求1所述索引拆分布魯姆過濾器的特征規(guī)則插入方法，其特征是采用一個刪除位圖用于記錄片外特征規(guī)則，刪除狀態(tài)；當(dāng)插入特征規(guī)則x時，隨機(jī)選擇刪除位圖中一個空缺位，即比特值為1，設(shè)置x的片外索引值為該空缺位的索引值，并在刪除位圖中設(shè)置該空缺位的比特值為0；統(tǒng)計刪除位圖中該空缺位之前且比特值為1的個數(shù)，從而計算x的片外物理地址；根據(jù)x的片外物理地址，在片外存儲器的相應(yīng)存儲位置上插入x，且其他特征規(guī)則的片外索引值保持不變；根據(jù)x的片外索引值，在每組片上并行CBF中插入x。

4、一種權(quán)利要求1所述索引拆分布魯姆過濾器的數(shù)據(jù)包內(nèi)容查詢方法，其特征是當(dāng)查詢數(shù)據(jù)包內(nèi)容x時，x哈希映射到片上并行計數(shù)布魯姆過濾器CBF；檢查x是否在所有片上并行CBF中，且每組片上并行CBF分別輸出b位比特值；合成所述b位比特值產(chǎn)生與x匹配的候選特征規(guī)則的片外索引值；直接訪問與該片外索引值對應(yīng)的特征規(guī)則，并與數(shù)據(jù)包內(nèi)容x進(jìn)行特征匹配。