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

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

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

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

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

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

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