[發明專利]一種估算滑動窗口下的數據流平均值的方法與系統

在審

• 申請號: 201410315983.8
• 申請日: 2014-07-02
• 公開（公告）號: CN104090952A
• 公開（公告）日: 2014-10-08
• 發明（設計）人: 王非;陳歲迪
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 武漢東喻專利代理事務所(普通合伙) 42224
• 代理人: 方放

技術領域

本發明屬于數據流分析技術領域，更具體地，涉及一種估算滑動窗口下的數據流平均值的方法與系統。

背景技術

近年來，數據流分析技術被廣泛應用到傳感器網絡通信，web服務器點擊日志、網絡安全監控與異常檢測、通話記錄、證券股票交易等領域，數據流分析已成為國內外各界研究的熱點。

數據流不同于傳統數據，不是存儲在磁盤上的有限數據集合，而是無限的、連續的、快速的、實時的，以流的形式出現的數據集合。實際應用中，存儲空間是有限的，但是數據流卻是源源不斷的到達。數據流的應用場景對實時性有較高要求，但是傳統的靜態數據挖掘往往需要多次掃描數據來獲得查詢結果，耗時較長。傳統的數據挖掘技術不能滿足動態的快速變化的數據流分析要求，數據流挖掘面臨著實時性、空間性和近似性等技術挑戰。

平均值的計算是數據流統計分析中的一個重要問題。但是目前的解決方法需要掃描窗口中的歷史數據而且需要保存一段窗口內的全部數據，對內存和計算能力要求較高，遠遠不能滿足源源不斷到達的無限的數據流以及實時性的應用要求，所以有必要提出基于單次掃描的實時計算方法。

發明內容

為了解決現有上述的技術問題，本發明需要提供一種能夠滿足實時性要求的估算滑動窗口下數據流平均值的方法與系統。

為了實現上述目的，按照本發明的一個方面，提供了一種估算滑動窗口下數據流平均值的方法，包括以下步驟：

(1)、初始化指數直方圖：所述指數直方圖把數據元素劃分到不同的層次上，每層由若干個桶組成，所述桶用來存儲數據流中一段時間內的數據集合信息，所述信息包括數據集合對應的時間戳和容量，所述時間戳表示的是數據集合中距離當前時刻最近的數據的時間戳，容量表示的是數據集合中所有數據元素的和；

(2)、將數據流的信息儲存在桶中：所述桶在指數直方圖中的位置由時間戳決定：層數越高，所述層上的桶的時間戳越舊，層數越低，所述層上的桶的時間戳越新；所述桶的時間戳越舊，表示桶中數據元素離當前時刻越遠；桶的時間戳越新，表示桶中數據元素離當前時刻越近；同一層中的桶按時間戳新舊順序排列；隨著數據的不斷流入，當有新的數據添加以及舊的數據刪除時，進行桶的合并與分解操作，合并分解規則以桶的容量為參考；

(3)、查詢指數直方圖，輸出近似平均值：首先計算指數直方圖中所有桶的容量之和SUM，如果指數直方圖只有一層，則輸出近似平均值計算公式為其中N是滑動窗口的大小；如果指數直方圖不只一層，則查詢時間戳最舊的桶的容量C，輸出近似平均值其計算公式為其中N是滑動窗口的大小。

本方法輸出的近似結果的最大相對誤差為1/k，其中k是用戶預定義的參數。

在本發明的一個實施例中，所述步驟(2)包括以下子步驟：

(2.1)、檢查是否存在已經超過當前滑動窗口的范圍的桶，如存在則從指數直方圖中刪除其信息；

(2.2)、從數據流中取出當前到達的數據項，根據用戶自定義的精度將數據流中當前到達的數據項轉換成整數值；如果轉換之后的數據不等于0，則執行步驟(2.3)；如果等于0，則不必執行步驟(2.3)；

(2.3)、更新指數直方圖中的桶存儲的信息，按照桶的分解合并規則對指數直方圖中的桶進行分解合并。

在本發明的一個實施例中，所述步驟(2.1)中檢查是否存在桶已經超過當前滑動窗口的時間范圍，具體的是通過檢查時間戳最舊的桶的時間戳與(t+1)mod(N)是否相等，若兩者相等，則表示時間戳最舊的桶超過了當前滑動窗口的時間范圍，其中t為當前時刻，N為窗口的大小，其中mod表示取兩個整數相除后結果的余數。

在本發明的一個實施例中，所述步驟(2.3)包括以下子步驟：

(2.3.1)、根據用戶自定義的精度將數據流中當前到達的數據項轉換成整數值；新建一個桶，時間戳為(t+1)mod(N)，容量為當前到達的數據項轉換后的值的大小，其中t為當前時刻，N為滑動窗口的大小，將所述桶插入到指數直方圖的最低層B₀中,用B_i表示指數直方圖中的第i層，i從0開始計數；然后從B₀層開始逐步檢查B_i層中所有桶的容量之和；