基于Bloom Filter技術(shù)的若干數(shù)據(jù)流處理算法.pdf

1、數(shù)據(jù)流模型的出現(xiàn)對(duì)數(shù)據(jù)的管理與分析提出了新的要求，如直接反映數(shù)據(jù)的本來(lái)面目、可以處理連續(xù)查詢(xún)、能夠處理異種數(shù)據(jù)、快速響應(yīng)用戶(hù)查詢(xún)等，其本質(zhì)是對(duì)數(shù)據(jù)流的管理和分析。因此，必須進(jìn)行數(shù)據(jù)流管理與分析新技術(shù)的研究，并且已經(jīng)成為當(dāng)前的一個(gè)研究熱點(diǎn)。典型的數(shù)據(jù)流管理與分析包括數(shù)據(jù)流采集與預(yù)處理、數(shù)據(jù)的特征抽取、數(shù)據(jù)聚集等基本連續(xù)查詢(xún)的分析與執(zhí)行、相關(guān)性檢測(cè)或預(yù)測(cè)與分類(lèi)等復(fù)雜的分析操作。研究數(shù)據(jù)流相關(guān)技術(shù)不僅有重要的學(xué)術(shù)價(jià)值，而且在傳感器網(wǎng)絡(luò)、氣象監(jiān)

2、測(cè)與分析、移動(dòng)物體位置跟蹤、股票分析、郵件過(guò)濾、網(wǎng)絡(luò)監(jiān)控與安全等領(lǐng)域有著巨大的應(yīng)用前景。本文對(duì)數(shù)據(jù)流在線(xiàn)分析的若干關(guān)鍵問(wèn)題進(jìn)行了深入探索，主要有以下內(nèi)容： (1)致力于滑動(dòng)窗口上副本檢測(cè)的研究，提出了一個(gè)基于計(jì)數(shù)型Bloom Filter的新的數(shù)據(jù)概要—Decaying Bloom Filter(DBF)和一個(gè)有效的概要?jiǎng)討B(tài)更新算法。DBF能夠通過(guò)保存元素的剩余壽命值來(lái)維護(hù)窗口的移動(dòng)，即，刪除過(guò)期的元素來(lái)保存新到達(dá)的元素。為了提

3、高概要的更新的速度和降低存儲(chǔ)空間，我們?cè)诟滤惴ㄖ幸肓朔謮K和延遲技術(shù)，已知空間G比特位和滑動(dòng)窗口大小W,DBF更新的平均時(shí)間復(fù)雜度為O(開(kāi)方G/W)。通過(guò)深入分析指出該方法只存在誤是錯(cuò)誤而沒(méi)有誤否錯(cuò)誤以及誤是錯(cuò)誤概率的最小上界。 (2)致力于數(shù)據(jù)流歷史數(shù)據(jù)的近似聚集查詢(xún)的研究；基于Bloom Filter提出了新的概要存儲(chǔ)模型Multi-Bloom Filters(MBF)。MBF能夠有效地支持時(shí)間范圍內(nèi)的歷史數(shù)據(jù)元素的成員關(guān)

4、系查詢(xún)和頻率查詢(xún)，同時(shí)，MBF具有很大的靈活性，它能夠支持對(duì)較新的歷史數(shù)據(jù)細(xì)的時(shí)間粒度的查詢(xún)；而且可以通過(guò)對(duì)較久遠(yuǎn)的MBF壓縮以節(jié)約存儲(chǔ)空間，同時(shí)能夠支持相對(duì)較近的數(shù)據(jù)粗的時(shí)間粒度的查詢(xún)。 (3)數(shù)據(jù)流中任意子集的副本無(wú)效并且時(shí)間衰減的和是一個(gè)用于分布式流下的各種分析的重要聚集。我們致力于此問(wèn)題并引入了新的解決方法，該方法不僅能夠檢測(cè)數(shù)據(jù)流中副本而且能夠根據(jù)用戶(hù)定義的衰減函數(shù)來(lái)動(dòng)態(tài)維持?jǐn)?shù)據(jù)流中不同元素的衰減權(quán)值。另外當(dāng)查詢(xún)數(shù)據(jù)流