基于屏蔽-匯總技術的數(shù)據(jù)流處理算法.pdf

1、與傳統(tǒng)數(shù)據(jù)密集型應用相比，諸如網(wǎng)絡監(jiān)控系統(tǒng)等順序產生的實時數(shù)據(jù)無法精確存儲在數(shù)據(jù)庫中，這種數(shù)據(jù)序列被稱為數(shù)據(jù)流。數(shù)據(jù)流的典型特點是，其存儲消耗具有潛在的無界性，其產生次序、間隔等統(tǒng)計特性具有不確定性，因此，數(shù)據(jù)流處理的算法需要具備以下的特點：1)算法復雜度必須是次線性的，輸出結果可以是近似的；2)算法能夠實時處理數(shù)據(jù)流輸入。線性復雜度算法不能處理數(shù)據(jù)流的存儲、查詢和分析處理，因此，通過屏蔽或匯總數(shù)據(jù)流來控制次線性復雜度存儲消耗成為數(shù)據(jù)流

2、研究的重要內容。本篇論文通過對數(shù)據(jù)流上頻繁項(集)發(fā)現(xiàn)、分布數(shù)據(jù)流并上聚合函數(shù)估算和k-中值點(k-median)搜尋，研究數(shù)據(jù)流處理的屏蔽和匯總的基本策略，主要貢獻有： 1．基于在線屏蔽策略，提出數(shù)據(jù)流上拒真的頻繁項(集)發(fā)現(xiàn)，使用O(s-1n(2δ-1))存儲以至少1-δ概率輸出頻繁項：使用O(K/δ1n(s-1δ-1))存儲可靠挖掘邊界頻繁項集(頻繁項集的濃縮表示)； 2．基于采樣屏蔽策略，提出濾除分布數(shù)據(jù)流中的冗

3、余和不一致的算法，應用min-wise哈希采樣數(shù)據(jù)流而獲取均勻樣本集。由于獲取的樣本集不受分布流中冗余和不一致數(shù)據(jù)影響，能夠準確估計聚合函數(shù)值，并進一步應用min—wise哈希方法采樣位置流(10cationstreams)來搜尋后一中值點； 3．基于匯總數(shù)據(jù)流策略，提出數(shù)據(jù)流上k-中值點的快速估算算法，應用空間分割的匯總結構控制存儲復雜度。不同于位置流中的頻繁更新，數(shù)據(jù)流上k-中值點需要單遍掃描龐大數(shù)目點集來獲取近似中值點集。