基于數(shù)據(jù)流的聚合函數(shù)精確計算研究及其應用.pdf

1、隨著網(wǎng)絡的不斷普及，流數(shù)據(jù)處理逐漸受到關注，流數(shù)據(jù)中的聚合計算也越來越重要。在傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)中，聚合函數(shù)定義為對一組值進行計算，并返回單個值的函數(shù)。在本文的研究中，我們仍然使用該定義。解決數(shù)據(jù)流中的聚合函數(shù)計算問題，對處理數(shù)據(jù)流，解決網(wǎng)絡中的監(jiān)控、統(tǒng)計、檢測等問題具有現(xiàn)實意義。 本文主要貢獻如下：(1)對輸入數(shù)據(jù)的類型為數(shù)值型的聚合函數(shù)，提出了一種存儲最少數(shù)據(jù)的MAX函數(shù)和MIN函數(shù)的精確計算方法。這種方法是一種基于數(shù)據(jù)流滑

2、動窗口聚合函數(shù)的精確增量式計算方法，它對于長度為N的輸入序列，算法的時間復雜度為O(N)；最壞情況下，空間復雜度為O(N)，最好情況下，復雜度為O(M)，其中，M為預先分配內存的大小。并通過數(shù)學理論分析和證明了該方法的正確性，還通過實驗檢驗了該方法的有效性和實用性。最后還實現(xiàn)了COUNT、SUM、AVG、STDEV、STDEP、VAR、VARP等聚合函數(shù)的計算方法——增量式計算方法。 (2)對輸入數(shù)據(jù)的類型為字符型的聚合函數(shù)，實

3、現(xiàn)了一種基于通用后綴樹(GST)表示的字符串頻率統(tǒng)計方法。該方法不需要任何訓練，直接對接收的文本進行統(tǒng)計，并根據(jù)字符串的頻率進行分類；對于長度為N的文本，算法的時間復雜度和空間復雜度均為O(N)。并應用對輸入數(shù)據(jù)的類型為字符型的聚合函數(shù)的精確計算方法實現(xiàn)了一種基于后綴樹的骨干網(wǎng)絡垃圾郵件檢測方法。該檢測方法采用通用后綴樹(GST)表示郵件文本；當新的郵件到達時，通過不定長統(tǒng)計方法計算該郵件和其他類別郵件的相似度，并確定郵件所屬類別，然后