[發(fā)明專利]一種基于改進Bloom Filter結(jié)構(gòu)的城市海量數(shù)據(jù)流快速冗余消除方法

無效

• 申請?zhí)枺?/td>: 201210516470.4
• 申請日: 2012-11-30
• 公開（公告）號: CN103116599A
• 公開（公告）日: 2013-05-22
• 發(fā)明（設計）人: 陳庭貴;許翀寰;戴俊彥
• 申請（專利權(quán)）人: 浙江工商大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;王利強

1.一種基于改進Bloom?Filter結(jié)構(gòu)的城市海量數(shù)據(jù)流快速冗余消除方法，其特征在于：包括以下步驟：?

1）基于Bloom?Filter結(jié)構(gòu)的數(shù)據(jù)集存儲：設定數(shù)據(jù)流表示為?

S_N=x₁,x₂,...,x_n，N為數(shù)據(jù)流中元素的個數(shù)，初始狀態(tài)時，Bloom?Filter是一個包含m位的位數(shù)組，每一位都置為0，如下所示：b[i]=0,i=0...m-1；Bloom?Filter使用k個相互獨立的哈希函數(shù)，它們分別將集合中的每個元素映射到(1,...,m)的范圍中，對任意一個元素x，第i個哈希函數(shù)映射的位置就會被置為1，即h_i(x)=1,1≤i≤k；?

2）海量動態(tài)數(shù)據(jù)集計數(shù)存儲方法：將標準Bloom?Filter位數(shù)組的每一位擴展為一個小的計數(shù)器,在插入元素時給對應的k個Counter的值分別加1，而在刪除元素時則給對應的k個Counter的值分別減1：?

3）老化元素加速處理機制：采用前后兩個計數(shù)窗口的跳躍窗口模式，首先定義兩個BF結(jié)構(gòu)體，即?

BFO[1,...,m]?

BFN[1,...,m]?

每個結(jié)構(gòu)體是由m個整數(shù)組成的數(shù)組；?

定義散列函數(shù)f₁,f₂,...,f_k為BF的k個散列映射；假定w為數(shù)據(jù)流老化計數(shù)值，BFO代表前一區(qū)間即[1,w]范圍內(nèi)的計數(shù)映射，BFN代表后一區(qū)間即[w+1,2w]范圍內(nèi)的計數(shù)映射；?

4）雙指針動態(tài)控制方法：采用雙動態(tài)指針的方法，指針能夠在BFO和BFN的移動區(qū)間中標志當前計數(shù)值，并為每一條數(shù)據(jù)流分配一個當前的計數(shù)標記，指針p_i具備有效計數(shù)區(qū)間[1,w]；?

5）新數(shù)據(jù)插入：當有新元素x_i需要插入時，將在BFO及BFN上先各進行k次散列映射，計算出相應數(shù)值，根據(jù)新數(shù)據(jù)在BFO及BFN上的相應數(shù)值，計算得出其相應的最小值：?

v=min(v₁,v₂,...,v_k)?

6）判斷新元素是否冗余：依據(jù)前一步計算得出的最小值，如果BFN對應的最小值v=0，則判定該元素并沒有在BFN所對應的工作區(qū)間中出現(xiàn)過；如果BFO對應的最小值v<p1，則表示該元素也沒有在前一工作區(qū)間中出現(xiàn)過；如果新元素x_i既沒有在BFO中出現(xiàn)過，也沒有在BFN中出現(xiàn)過，則加入該新元素，否則丟?棄該冗余元素；?

7）更新數(shù)據(jù)流計數(shù)：在BFN中為該數(shù)據(jù)流對應的k個位置設置成當前的指針計數(shù)器值，即b[i]=p2；?

8）定期刪除歷史數(shù)據(jù)：在動態(tài)指針p1達到臨界值w時，表示該數(shù)據(jù)流已經(jīng)成為老化流，因此刪除BFO，并更換BFO和BFN，使BFO繼續(xù)保持上一工作區(qū)間的數(shù)據(jù)流映射，BFN保存當前工作區(qū)間的數(shù)據(jù)流映射，同時初始化p_i=1；?

9）若無新數(shù)據(jù)到達則輸出冗余優(yōu)化后結(jié)果數(shù)據(jù)流。?