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

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

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

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