基于移動指針的數(shù)據(jù)流冗余消除算法

唐海娜，林小拉，韓春靜

(1.中山大學 信息科學與技術學院，廣東 廣州 510006；2.中國科學院 計算機網(wǎng)絡信息中心，北京 100190)

1 引言

近年來，伴隨著互聯(lián)網(wǎng)技術與應用的迅猛發(fā)展，視頻分發(fā)、文件共享、網(wǎng)頁瀏覽、傳感器探測數(shù)據(jù)、娛樂游戲等網(wǎng)絡流量呈現(xiàn)持續(xù)高速增長態(tài)勢。網(wǎng)絡數(shù)據(jù)流(data streaming)[1,2]是按時間遞增順序排列且具有相同屬性的數(shù)據(jù)分組序列，主要表現(xiàn)有實時性、連續(xù)性、單遍性、無限性等特征。目前，針對數(shù)據(jù)流的分析被日益廣泛地應用于網(wǎng)絡安全監(jiān)測、負載均衡、緩存策略等領域。

研究發(fā)現(xiàn)，網(wǎng)絡數(shù)據(jù)流存在大量的冗余，如文獻[3]中研究了企業(yè)網(wǎng)主干鏈路流量組成，發(fā)現(xiàn)入方向存在約20%的數(shù)據(jù)冗余，出方向存在約50%的數(shù)據(jù)冗余。導致這一現(xiàn)象的原因有很多，如大量用戶訪問同樣的Web資源，或采用P2P交換視頻資源等。為了降低資源消耗，提高處理性能，目前數(shù)據(jù)流冗余消除技術已成為一個熱門的研究課題。數(shù)據(jù)流冗余消除是指通過單次遍歷從數(shù)據(jù)流無窮序列中識別出已出現(xiàn)過的數(shù)據(jù)對象并區(qū)別處理[4]。這一問題的研究有著廣泛的應用價值，例如，網(wǎng)頁爬蟲中的去重問題[5]，互聯(lián)網(wǎng)廣告運營中的“惡意偽點擊”監(jiān)測問題[6]，以及電信話單中重復通話記錄消除[7]等。此外，在大規(guī)模分布式協(xié)作的網(wǎng)絡測量中，同一高速網(wǎng)絡的監(jiān)測由多個監(jiān)測探針共同完成，需要完成不同業(yè)務流監(jiān)測的任務分配管理，數(shù)據(jù)流冗余消除也是其中的關鍵技術[8～10]。

數(shù)據(jù)流冗余消除技術的研究中面臨如下問題與挑戰(zhàn)：首先，高數(shù)據(jù)分組傳輸速率與大并發(fā)數(shù)據(jù)流需要快速掃描，無法使用傳統(tǒng)的多遍掃描冗余檢測方法，必須通過單次遍歷實時監(jiān)測數(shù)據(jù)流冗余記錄。其次，由于數(shù)據(jù)流的無限性特征，不可能把所有歷史數(shù)據(jù)都保存在內存中處理，一般取最近一段時間內的數(shù)據(jù)對象作為數(shù)據(jù)流冗余消除的有效范圍，在有限的內存空間中進行近似計算。因此準確性是數(shù)據(jù)流冗余消除算法的重要指標。如何兼顧準確性及處理性能是目前數(shù)據(jù)流冗余消除算法的研究重點。目前已有算法中，Stable Bloom filter[5]算法盡管可以實現(xiàn)O(n)的時間復雜度，但同時帶來假陽性以及假陰性誤差。Decaying Bloom filter[11]算法在Stable Bloom filter算法的基礎上提升了準確性，但它需要對Bloom filter結構體的反復掃描，從而需要O(m·n)的查詢時間復雜度，無法滿足高速網(wǎng)絡環(huán)境海量數(shù)據(jù)的實時處理需求。如何在高速增長的網(wǎng)絡環(huán)境下，設計準確、實時的數(shù)據(jù)流冗余消除算法成為當前學術界面臨的一大挑戰(zhàn)。

本文針對已有的數(shù)據(jù)流冗余消除算法時間復雜度高、誤判率高的問題，提出了一種基于移動指針的數(shù)據(jù)流冗余消除算法——SKIP Bloom filter。它采用動態(tài)指針在移動區(qū)間中標志當前的計數(shù)值，并為每一條數(shù)據(jù)流分配一個當前的計數(shù)標記符，以此避免了對Bloom filter結構的頻繁掃描，并保持了Bloom filter的準確性。本文論證了算法具有O(n)的時間復雜度和O(1-(1- 1/(2m))w·k)k的假陽性誤判率，與以往算法相比具有明顯的性能及準確度優(yōu)勢。

2 相關工作

基于海量數(shù)據(jù)的數(shù)據(jù)流冗余消除算法設計具有極大的挑戰(zhàn)。最通常的方法采用Buffer存儲所有歷史數(shù)據(jù)[12]，通過逐行記錄比較得到精確計算結果。這種方法精度高，但需要大存儲開銷，處理效率低，在實際網(wǎng)絡環(huán)境中應用困難。為提高處理性能，可以使用數(shù)據(jù)庫存儲的方式，通過基于散列的算法或基于排序的算法[13]進行冗余消除，但一般需多次遍歷所有記錄，因此，隨著數(shù)據(jù)流不斷增長，這些方法很難滿足高效查詢的需求。

BF(Bloom filter)[14]是一種允許存在一定誤判情況下存儲空間高效的散列結構，它在查詢準確率和存儲代價之間具有較好的折衷，目前被廣泛應用于Web緩存、P2P網(wǎng)絡協(xié)作以及網(wǎng)絡測量等領域。BF對集合采用一個位串表示，既支持集合元素查詢，又能有效地過濾掉不屬于集合的元素。其算法結構的實質是將集合中的元素通過k個散列函數(shù)映射到位串向量中，來判斷一個元素是否已屬于某個集合。由于散列查找的常數(shù)時間和存儲空間開銷較小，BF算法具有很好的存取性能，因此近年來被研究人員應用于數(shù)據(jù)流的冗余消除問題。

傳統(tǒng)BF基于靜態(tài)數(shù)據(jù)集設計，只支持插入與查詢操作。為了支持動態(tài)數(shù)據(jù)集，文獻[15,16]等提出了Counting BF算法，它采用計數(shù)方式取代了原來的“0/1”存儲，可以支持對元素的刪除操作。Counting BF在應用于數(shù)據(jù)流冗余消除問題時，可以存放時間計數(shù)(time-based)或元素計數(shù)(counterbased)，目前已經提出的算法大部分是基于元素計數(shù)的方式。數(shù)據(jù)流冗余消除算法設計的關鍵問題是需實時刪除達到最大計數(shù)值的過期元素。由于數(shù)據(jù)流的單遍特性，Counting BF結構在應用于數(shù)據(jù)流冗余消除問題時缺乏刪除觸發(fā)條件。因此目前研究人員基于Counting BF，定義有效窗口區(qū)間，提出了一系列數(shù)據(jù)流冗余消除算法。基本上可以分為以下3類[6]。

1) 基準窗口 (landmark window) 模式：基于時間或計數(shù)范圍把數(shù)據(jù)流分成若干段，每個段內維護N個元素，段內所有元素的到期時間相同。算法維持一個當前段，當計數(shù)到期時，自動刪除當前段，并繼續(xù)在下N個元素上處理。

2) 滑動窗口 (sliding window) 模式：窗口保存最近的N個元素，每個新元素到來或舊元素過期都會更新窗口。由于sliding window中的元素都會依次到期，因此通常需要為每個元素維持一個序號以方便計算到期時間。

3) 跳躍窗口 (jumping window) 模式：最先在文獻[17]中被提出，介于landmark window與sliding window之間?；舅枷胧前岩粋€大的窗口切成若干子窗口，每個子窗口表示一個確定的時間段/計數(shù)范圍的數(shù)據(jù)。一旦所有子窗口滿，刪除最老的子窗口，并創(chuàng)建最新的子窗口。通過對子窗口的信息進行綜合得到總體信息。

Metwally在文獻[6]中采用BF算法檢測點擊流(click stream)中的重復點擊問題，來判斷廣告點擊是來自人還是機器。論文主要針對landmark window模式采用原始BF結構進行冗余檢測，這種方法隨著數(shù)據(jù)流的無限增長最終BF結構會變“滿”(即所有位都為1)，因此不具備可操作性。Deng F與Rafiei D在文獻[5]中基于sliding window方式研究了數(shù)據(jù)流序列重復性近似檢測問題，提出了 stable BF算法，通過引入概率因子 p，把每次插入新數(shù)據(jù)時的輪詢更新范圍限制在p，并證明了算法可以維持BF的0元素比例在一個穩(wěn)定的范圍。但p因子的引入帶來假陽性以及假陰性誤判率，同時加重了算法的復雜度。

文獻[11]提出了decaying BF (DBF)算法，每次插入新元素時需要掃描BF結構體中所有非零元素并減1，因此單元素插入的時間復雜度是O(m)，其中m為BF結構體長度，這對于很多高速應用是不可接受的。此外，還有Zhang等提出的timing BF算法[18,19]，BF結構體中每個計數(shù)含bit，其中，w為窗口大小，c是一個常量。定義時間戳t的取值范圍為從0～w+c-1，并從中取w個連續(xù)的值，即(t-w+1)～t表示當前窗口。每次新元素到來時只需檢查BF中m/c個位置以消除過期元素，經c次后完成一輪對BF結構體的完整掃描。Timing BF算法的核心思想是利用額外空間 c來提升處理性能，因此消耗了更多的內存，同時單元素插入的時間復雜度仍為O(m/w)。

因此，目前已有算法主要采用滑動窗口模式，算法的主要開銷在于需要實時監(jiān)測和刪除過期元素。如decay Bloom filter算法通過對BF結構體中m個元素的全掃描實現(xiàn)過期元素的及時刪除，因而加大了算法的時間復雜度。而stable Bloom filter算法通過引入概率因子提升了處理性能，但帶來一定的假陰性誤差。本文針對已有的數(shù)據(jù)流冗余消除算法時間復雜度高/誤報率高的問題，提出了一種基于移動指針的數(shù)據(jù)流冗余消除算法——SKIP BF。它采用動態(tài)指針在移動區(qū)間中標志當前的計數(shù)值，并為每一條數(shù)據(jù)流分配一個當前的計數(shù)標記符。SKIP BF算法引入雙BF結構區(qū)分歷史數(shù)據(jù)與當前數(shù)據(jù)，通過定期刪除歷史數(shù)據(jù)避免了對BF結構的頻繁掃描，并保持了BF的準確性。

3 數(shù)據(jù)流冗余消除算法設計與分析

3.1 問題定義

假定數(shù)據(jù)流可表示為SN=x1, x2,…, xN，N為數(shù)據(jù)流元素個數(shù)，并趨于無窮大。假定xi出現(xiàn)后，在w個計數(shù)范圍內出現(xiàn)的元素被認為是xi的重復元素。則數(shù)據(jù)流冗余消除問題相關定義如下。

定義 1 (數(shù)據(jù)流冗余消除)給定數(shù)據(jù)流無窮序列SN，假定w為數(shù)據(jù)流老化計數(shù)值。定義B為保存SN歷史元素及其計數(shù)序號的結構體。數(shù)據(jù)流冗余消除問題可表示為：

任取 xi∈SN，假設 xi∈{xi-w,xi-w+1,…, xi-1}，即該元素為冗余元素，則 Duplicate(xi) = true，調用Reject(xi)丟棄該元素，并更新B的狀態(tài)；否則調用do(xi)處理該元素，并向B中插入新的項xi。

定義 2 (錯誤概率)給定數(shù)據(jù)流無窮序列 SN，假定w為數(shù)據(jù)流老化計數(shù)值。錯誤概率的定義如下：

任取 xi∈SN，假設 xi?{xi-w,xi-w+1,…,xi-1}，即該元素為非冗余元素，若算法計算Duplicate(xi) = true，則為假陽性錯誤。假設 xi∈{xi-w,xi-w+1,…,xi-1}，即該元素為冗余元素，若算法計算 Duplicate(xi) =false，則為假陰性錯誤。錯誤概率記作?fe，稱為假陽性錯誤概率(false positive rate)或假陰性錯誤概率(false negative rate)。

3.2 算法描述

本文提出的SKIP BF算法稱為基于移動指針的BF 算法。為了避免sliding window模式需要實時掃描整個BF結構體以刪除過期元素所帶來的性能開銷，SKIP BF算法設計采用前后 2個計數(shù)窗口的jumping window模式，同時提出了雙BF之間的輪流切換及定時刪除機制以加速對過期元素的處理，并以此實現(xiàn)了良好的算法準確性。

SKIP BF算法定義2個BF結構體，每個結構體是由 m 個整數(shù)組成的數(shù)組，即 BFO[1,…,m]和BFN[1,…,m]。其中，BFO為old BF, BFN為new BF。定義散列函數(shù)h1, h2, …, hk為BF的散列映射。假定w為數(shù)據(jù)流老化計數(shù)值。則SKIP BF算法中，BFO代表前一區(qū)間即[1, w]范圍內的計數(shù)映射，BFN代表后一區(qū)間即[w+1，2w]范圍內的計數(shù)映射。BF結構中m個整數(shù)為計數(shù)。設定數(shù)據(jù)流算法的動態(tài)控制指針p，它具備有效計數(shù)區(qū)間[p-w，p]。p的最大值為2w，即計數(shù)的最大范圍，具體如圖1所示。

圖1 SKIP Bloom filter原理示意

SKIP Bloom filter算法可以表示如下：

Algorithm: SKIP Bloom filter算法

輸入：數(shù)據(jù)流無限序列S=S1,S2,…,SN, N?∞

輸出：為數(shù)據(jù)流中的每個元素輸出“Yes/No”，表示該元素是否在BF中有效存在

Begin

初始化BFO[1]…BFO[m]=0;

初始化BFN[1]…BFN[m]=0;

算法說明如下：SKIP BF算法把計數(shù)空間[1,2w]分成 2個區(qū)域，分別是[1,w]和[w+1,2w]。定義BFN為當前工作區(qū)間，定義BFO為上一工作區(qū)間。對于每個要添加的元素，計算它的k個BF散列值，并更新到BFN中。在更新時，為了節(jié)省空間以及保持計算的連續(xù)性，指針p的取值固定在[1,w]。所以判斷新元素是否在最近 w個計數(shù)范圍出現(xiàn)過的方法為：判斷 BFN中對應 k個值是否都大于1，或者判斷BFO中對應k個值是否都大于p。因此，SKIP BF可以重新表示為圖 2。

圖2 SKIP Bloom filter實際設計示意

當p到達臨界值w時，表示BFO中的流已經成為老化流。因此刪除BFO，并對換BFO與BFN，使 BFO繼續(xù)存放上一工作區(qū)間的數(shù)據(jù)流映射，并使用 BFN保存當前工作區(qū)間的數(shù)據(jù)流映射。同時重新初始化p=1。

新數(shù)據(jù)插入：當新元素xi需要插入時，算法基于2k次散列，得到該元素在BFO及BFN中的對應值。對于每一新元素的2組對應值，算法計算得到每組的最小值v=min(v1,v2,…,vk)。如果 BFN對應的最小值 v=0，則該元素沒有在當前工作區(qū)間出現(xiàn)過。如果BFO對應的最小值 v＜p，則表示沒有在前一工作區(qū)間出現(xiàn)過。如果新元素xi既沒有在 BFO 中出現(xiàn)過，也沒有在BFN中出現(xiàn)過，則處理該新元素，否則丟棄該冗余元素。然后在BFN中為該數(shù)據(jù)流對應的 k個位置設置成當前的指針計數(shù)器，即 p。

舉例如下：在圖3中，設定數(shù)據(jù)流SN，BF分別為BFO以及BFN。每個BF的長度為m(m=12)，對應的散列個數(shù)k=4。設定計數(shù)臨界值為w=16。當xi要插入時，p為8。4次散列后對應的值分別是{5，3，3，8}以及{4，0，5，6}。明顯可以看出在當前工作區(qū)間BFN未出現(xiàn)過該元素。在上一工作區(qū)間BFO對應的最小值為3，小于當前指針值 8，因此上一工作區(qū)間也未存在該元素的有效計數(shù)值，因此該元素未存在冗余，即在BFN中更新4個相應的位置為8。

圖3 新數(shù)據(jù)插入處理示意

3.3 算法性能分析

SKIP BF算法把整個計數(shù)范圍以2w個計數(shù)分段為2個不同的區(qū)間，每個區(qū)間分別表示前半段的計數(shù)映射情況以及后半段的計數(shù)映射情況。每插入一個元素時，依次比較該元素是否在前半段中出現(xiàn)過，以及是否在后半段中出現(xiàn)過。算法的核心在于定期刪除前半段的計數(shù)，從而避免了對BF結構的頻繁掃描，且保障了SKIP BF中記錄的一直為最近2w個計數(shù)范圍內的映射情況。從SKIP BF算法描述上可以看出，每更新一個元素，需要2k次散列及k次賦值，因此，單元素插入需要3k次操作。由于k為常數(shù)，算法的時間復雜度可表示為O(n)。

當集合S={x1,x2,…,xn}的所有元素都被k個散列函數(shù)映射到2個m長度的位數(shù)組時，BFO和BFN中某一位在過去w個計數(shù)中被未訪問過的概率為：(1- 1/(2m))w·k，因此SKIP BF算法的假陽性錯誤概率為O(1-(1- 1/(2m))w·k)k。其中，m為BF的數(shù)組長度，w為數(shù)據(jù)流老化計數(shù)值，k為散列個數(shù)。

如果某元素在過去w個計數(shù)中出現(xiàn)過，一定存在BFO中對應指針計數(shù)器值大于p或者BFN中對應指針計數(shù)器值大于0，也就是說SKIP BF不會返回不存在，因此算法的假陰性錯誤概率為0。

基于對SKIP BF算法的性能分析，本文對比了已提出的幾個冗余消除算法，見表1。其中，n為數(shù)據(jù)流集合S={x1,x2,…,xn}的元素個數(shù)，m為BF結構體的長度，w或Max為BF結構體的單元最大值，p為Stable BF算法中的特定因子。從表中可以看出，相對于其他算法，SKIP BF算法與stable BF算法具有更優(yōu)的時間復雜度，但stable BF因p引子的引入帶來假陰性誤判率。此外，在空間消耗上，SKIP BF的空間消耗約為stable BF以及decay BF的2倍，Timing BF算法的空間消耗則隨c值的選取而動態(tài)變化。

表1 數(shù)據(jù)流冗余消除算法性能比較

4 實驗驗證

本文實現(xiàn)了SKIP BF算法、decay BF算法以及Buffer算法，算法的實現(xiàn)部分參考文獻[20]給出的代碼。Buffer算法沿用文獻[5]中的buffer方法，即在內存中開辟一塊buffer, 存放目前w計數(shù)范圍內的有效數(shù)據(jù)流。每新來一個元素，查找該元素有沒有在該buffer中存在，如果存在則冗余消除，否則加入該元素，并刪除buffer中w計數(shù)范圍之前的元素。為方便buffer中元素的增刪，該buffer采用指針管理。

實驗基于中國科技網(wǎng)(China science and technology network) 實際網(wǎng)絡環(huán)境，從骨干路由器上收集netflow流數(shù)據(jù)進行測試。實驗分析的目標是在數(shù)據(jù)源一定的情況下，分析驗證SKIP BF算法和decay BF算法在m、k發(fā)生變化時對假陽性誤判率的影響及相互的對比。其中，誤判率的比較以buffer算法作為準確的冗余消除值，其他2個算法與該算法進行比較得到最終的誤判率。實驗分10次進行，分別采集4h、8h、12h…40h的數(shù)據(jù)流。實驗機器配置為3臺IBM 3650服務器，2.13GHz主頻的雙核4×CPU，內存大小為24GB。

1) m動態(tài)變化時誤判率分析

相對于buffer算法，SKIP BF算法以及decay BF算法會產生一定的假陽性誤判。圖4給出在10次實驗中，選取k=4，并動態(tài)改變m(m取值分別為4 096，8 192，16 384，65 536)，得到的算法假陽性誤判率的分析結果。從圖4可以看出，m增大時，SKIP BF算法及decay BF算法的假陽性誤判率明顯降低，這是因為m增大時，散列映射的沖突機率隨之降低。其中，SKIP BF算法誤判率下降的幅度更大。對于同樣的 m，Decay BF算法的假陽性誤判率明顯高于SKIP BF算法，約為SKIP BF算法的2～12倍。

圖4 m變化時不同算法的假陽性錯誤概率

2) k動態(tài)變化時誤判率分析

本實驗驗證選取m=8 192時，動態(tài)改變k=4，k=8，k=12，k=16進行比較，查看k動態(tài)變化時兩算法的性能對比情況。從圖5可以看出，k=4時，2個算法具有更優(yōu)的假陽性誤判率。在相同的 k值下， Decay BF算法的假陽性誤判率明顯高于 SKIP BF算法，約為SKIP BF算法的3～11倍。但總體上，k對假陽性誤判率的影響遠遠低于m變化時產生的影響。

圖5 k變化時不同算法的假陽性錯誤概率

5 結束語

隨著網(wǎng)絡的高速化發(fā)展，數(shù)據(jù)流冗余消除問題需要滿足實時性和高效性的需求。目前存在的stable BF算法以及decaying BF算法存在較高的更新開銷和假陽性誤判等問題。本文提出了一種基于移動指針的數(shù)據(jù)流冗余消除算法，其核心思想是：設計 2個 BF，分別表示前半計數(shù)區(qū)間的有效計數(shù)元素以及后半計數(shù)區(qū)間的有效計數(shù)元素。定義動態(tài)指針p來構建當前有效工作區(qū)間(p-w, p)。每插入一個元素，判斷其在當前有效工作區(qū)間是否存在。算法最核心的設計是采用在區(qū)間邊界刪除前半段計數(shù)歷史的方式，以取代stable BF等算法對結構的頻繁掃描，從而保證了算法的高效性和穩(wěn)定性。本文通過理論分析和實驗驗證證明了算法具有更優(yōu)的插入/查詢效率以及更優(yōu)的誤判率。SKIP BF算法是一種高效的數(shù)據(jù)結構，可廣泛應用于數(shù)據(jù)分組分類、網(wǎng)頁爬蟲去重以及流量監(jiān)測與分析等高速數(shù)據(jù)分組處理等場景。

基于本文的工作，可以進一步研究如何優(yōu)化算法的空間存儲性能。當前，針對BF結構體的存儲壓縮技術研究[16,21,22]已有很多進展，可以應用到數(shù)據(jù)流冗余消除技術中。此外，結合多核處理器的并行算法研究[23,24]也是提升數(shù)據(jù)流冗余消除性能的另一方向。

[1] BABCOCK B, BABU S, DATAR M. Models and issues in data streams[A]. Proc of the 21st ACMSIGACT-SIGMOD-SIGART Symp on Principles of Database Systems[C]. Madison: ACM Press, 2002.1-16.

[2] 金澈清, 錢衛(wèi)寧, 周傲英. 流數(shù)據(jù)分析與管理綜述[J]. 軟件學報,2004 , 15 (8) : 1172-1181.JIN C Q, QIAN W N, ZHOU A Y. Analysis and management of streaming data: a survey[J]. Journal of Software, 2004, 15 (8):1172-1181.

[3] ANAND A, MUTHUKRISHNAN C, AKELLA A. Redundancy in network traffic: findings and implications[A]. Proc of SIGMETRICS[C]. Seattle, WA, USA, 2009.37-48.

[4] WANG X, ZHANG Q, JIA Y. Efficiently filtering duplicates over distributed data streams[A]. International Conference on Computer Science and Software Engineering (CSSE)[C]. 2008. 631-634.

[5] F. DENG, D. RAFIEI. Approximately detecting duplicates for streaming data using stable bloom filters[A]. Proc 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD) [C]. Chicago, Illinois, USA, 2006.25-36.

[6] METWALLY D, AGRAWAL A E. ABBADI. Duplicate detection in click streams[A]. Proc 14th International World Wide Web Conference (WWW)[C]. Chiba, Japan, 2005.12-21.

[7] V. GARG, A. NARANG, S. BHATTACHERJEE. Real-time memory efficient data redundancy removal algorithm[A]. CIKM[C]. 2010.1259-1268.

[8] SEKAR V, REiTER M K, WILLINGER W. CSAMP: a system for network-wide flow monitoring[A]. Proceedings of the 5th USENIX Sympo-sium on Networked Systems Design and Implementation.Berkeley[C]. CA, USA: USENIX Association, 2008. 233-246.

[9] SHARMA M, BYERS J. Scalable coordination techniques for distributed network monitoring[A]. Passive and Active Measurement Conference[C]. 2005. 349-352.

[10] COPPENS J, MARKATOS E, NOVOTNY J. Scampi - a scalable monitoring platform for the internet[A]. International Workshop on Inter-Domain Performance and Simulation(IPS)[C]. Budapest, Hungary, 2004.

[11] SHEN H, ZHANG Y. Improved approximate detection of duplicates for data streams over sliding windows[J]. Journal of Computer Science and Technology, 2008, 23(6): 973-987.

[12] GARCIA-MOLINA H, ULLMAN J D, WIDOM J. Database System Implementation[M]. Inc, Upper Saddle River, New Jersey, 2000.

[13] GRAEFE G, LINVILLE A, SHAPIRO L D. Sort vs. hash revisited[J].IEEE Transactions on Knowledge and Data Engineering, 1994,6(6):934-944.

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

[15] FAN L, CAO P, ALMEIDA J, BRODER A Z. Summary cache: a scalable wide-area Web cache sharing protocol[J]. IEEE-ACM Trans on Networking, 2000,8(3):281-293.

[16] FLAVIO B, MICHAEL M, RINA P, et al. An improved construction for counting Bloom filters[A]. Proc of the 14th Conf on Annual European Symp[C]. Zurich: Springer-Verlag, 2006. 684-695.

[17] ZHU Y, SHASHA D. StatStream: statistical monitoring of thousands of data streams in real time[A]. Proceedings of the 28th ACM VLDB International Conference on Very Large Data Bases[C]. 2002.358-369.

[18] ZHANG L F, GUAN Y. Detecting click fraud in pay-per-click streams of online advertising networks[A]. Proc 28th IEEE International Conference on Distributed Computing Systems (ICDCS)[C]. Beijing,China, 2008. 77-84.

[19] LINFENG ZHANG. Effective Techniques for Detecting and Attributing Cyber Criminals[D]. Iowa State University, 2008.

[20] MATTHIAS VALLENTIN. LIBBF, a header-only C++11 library that implements various types of of Bloom filters [EB/OL]. http://matthias.vallentin.net/libbf/.

[21] MITZENMACHER M. Compressed bloom filters[J]. IEEE/ACM Transactions on Networking, 2002, 10(5): 604-612.

[22] FICARA D, GIORDANO S, PROCISSI G. Multilayer compressed counting bloom filters[A]. Proceedings of the 27th Conference on Computer Communications[C]. 2008.

[23] BHATTACHERJEE S, NARANG A, GARG V K. High throughput data redundancy removal algorithm with scalable performance[A]. Proceedings of the 6th International Conference on High Performance and Embedded Architectures and Compilers[C]. Heraklion, 2011. 87-96.

[24] GARG V, NARANG A, BHATTACHERJEE S. Real-time approximate range motif discovery & data redundancy removal algorithm[A].Proceedings of the 14th International Conference on Extending Database Technology[C]. Uppsala, Sweden, 2011. 485-496.