流數(shù)據(jù)統(tǒng)計算法研究.pdf

1、流數(shù)據(jù)是近年來出現(xiàn)的一種新型的數(shù)據(jù)模型，在許多應(yīng)用領(lǐng)域出現(xiàn)頻繁，表現(xiàn)形式各異，例如：網(wǎng)絡(luò)監(jiān)測時的IP數(shù)據(jù)包、股票分析時的股票信息、電信公司的通話記錄、傳感器網(wǎng)絡(luò)發(fā)送的信號等等。與傳統(tǒng)的數(shù)據(jù)模型相比，流數(shù)據(jù)具有如下特點：實時到達(dá)，速率多變；連續(xù)到達(dá)，次序獨立；規(guī)模宏大，不能預(yù)知其極值；一經(jīng)處理，除非特意保存，否則不能再次取出處理。這些特點導(dǎo)致了流數(shù)據(jù)不能全部保存，只能實時地單遍訪問。與傳統(tǒng)數(shù)據(jù)庫應(yīng)用系統(tǒng)相比，流數(shù)據(jù)應(yīng)用系統(tǒng)往往需要支持連續(xù)

2、查詢和近似結(jié)果統(tǒng)計。因此，無法利用傳統(tǒng)數(shù)據(jù)庫技術(shù)有效地管理流數(shù)據(jù)，越來越多的研究人員開始對流數(shù)據(jù)的相關(guān)問題進(jìn)行研究。 流數(shù)據(jù)的統(tǒng)計反映了流數(shù)據(jù)的當(dāng)前狀態(tài)，在許多決策系統(tǒng)中扮演著重要的角色，同時也是流數(shù)據(jù)挖掘的一個重要基礎(chǔ)。由于流數(shù)據(jù)的獨特性，傳統(tǒng)統(tǒng)計算法不適用于流數(shù)據(jù)。因此，流數(shù)據(jù)統(tǒng)計已成為一個迫切需要解決的問題。 基于滑動窗口模型，給出了一種優(yōu)化的指數(shù)級直方圖--松散性指數(shù)級直方圖和結(jié)構(gòu)維持算法。利用對數(shù)空間，該方案解

3、決了流數(shù)據(jù)的實時近似求和問題，相比已有方法，有明顯的時空優(yōu)勢。把松散性指數(shù)級直方圖應(yīng)用到流數(shù)據(jù)計數(shù)問題上，充分考慮了流數(shù)據(jù)的相似度，定義了相似度函數(shù)，設(shè)計了一種系統(tǒng)框架，給出了一種解決最近N個流數(shù)據(jù)元素個數(shù)統(tǒng)計問題的算法，該算法保證相對誤差不大于指定閾值，且流數(shù)據(jù)相似度越大，時空優(yōu)勢越明顯。對于最大（?。┲档慕y(tǒng)計問題，設(shè)計了一種算法，該算法利用鏈?zhǔn)浇Y(jié)構(gòu)，動態(tài)維護(hù)當(dāng)前活動窗口中的最大值，針對內(nèi)存利用過大的情況，給出了壓縮策略，該算法利用少

4、量的空間，解決了滑動窗口模型下的流數(shù)據(jù)最大值統(tǒng)計問題。 相比聚集統(tǒng)計，熱門元素統(tǒng)計更能準(zhǔn)確地描述流數(shù)據(jù)的當(dāng)前狀態(tài)。給出了兩種單遍訪問算法--梯形過濾算法和波浪篩選算法，解決了滑動窗口模式下的流數(shù)據(jù)熱門元素統(tǒng)計問題，保證統(tǒng)計結(jié)果不會遺漏任何滿足條件的熱門元素。梯形過濾算法應(yīng)用指數(shù)級直方圖來統(tǒng)計流數(shù)據(jù)元素的出現(xiàn)次數(shù)，對直方圖實行周期性的壓縮以刪除不需要的元素和統(tǒng)計，該算法尤其適于分布不均勻的流數(shù)據(jù)，在此情況下，即使滑動窗口的尺寸增加

5、，候選數(shù)據(jù)集尺寸仍保持穩(wěn)定。波浪篩選算法通過對子窗口進(jìn)行周期性地創(chuàng)建和刪除，來統(tǒng)計元素的出現(xiàn)次數(shù)，其中每個子窗口擁有一個獨立的概要數(shù)據(jù)結(jié)構(gòu)，對每一次查詢，該算法保證輸出的數(shù)據(jù)個數(shù)不會過多。 相比前兩種統(tǒng)計，密度估計更能詳實地反映流數(shù)據(jù)的當(dāng)前狀態(tài)--流數(shù)據(jù)的分布特點。基于核心密度估計法，給出了一種適合流數(shù)據(jù)特點的密度估計算法。該算法利用遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)長度的空間，通過對流數(shù)據(jù)進(jìn)行窗口劃分，為單個窗口保留少量的分布信息，再綜合所有窗口信

6、息，從而對流數(shù)據(jù)的密度分布進(jìn)行實時評估。 以上的統(tǒng)計都反映了流數(shù)據(jù)的當(dāng)前狀態(tài)，而沒有描述出流數(shù)據(jù)狀態(tài)的變化情況，為此設(shè)計了一種流數(shù)據(jù)變化檢測方案。該方案采用在兩個相鄰窗口中出現(xiàn)次數(shù)變化大的元素來描述流數(shù)據(jù)的變化：首先，把單個窗口中的流數(shù)據(jù)劃分成若干層，在每層上對元素值域進(jìn)行分段；然后，在每層上定義若干分段集合，并對分段集合進(jìn)行求和運算；最后，通過對兩個窗口的概要結(jié)構(gòu)進(jìn)行合并，利用集合分解，求得出現(xiàn)次數(shù)變化大的元素，以描述流數(shù)據(jù)的