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

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

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

3、高概要的更新的速度和降低存儲空間，我們在更新算法中引入了分塊和延遲技術，已知空間G比特位和滑動窗口大小W,DBF更新的平均時間復雜度為O(開方G/W)。通過深入分析指出該方法只存在誤是錯誤而沒有誤否錯誤以及誤是錯誤概率的最小上界。 (2)致力于數(shù)據(jù)流歷史數(shù)據(jù)的近似聚集查詢的研究；基于Bloom Filter提出了新的概要存儲模型Multi-Bloom Filters(MBF)。MBF能夠有效地支持時間范圍內(nèi)的歷史數(shù)據(jù)元素的成員關

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