[發明專利]基于時間滑動窗口的數據流點連接查詢方法

有效

• 申請號: 201310219213.9
• 申請日: 2013-06-04
• 公開（公告）號: CN103309966A
• 公開（公告）日: 2013-09-18
• 發明（設計）人: 王坤朋;王偉平;木偉民;孟丹
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京輕創知識產權代理有限公司 11212
• 代理人: 楊立

技術領域

本發明涉及計算機領域的數據流連接方面，尤其涉及基于時間滑動窗口的數據流點連接查詢方法。

背景技術

近年來隨著信息技術的發展，一種稱為數據流的數據類型出現在越來越多的應用中，這類數據的特點是連續不斷、產生速度快、實時變化。各類應用中經常對數據流進行各類操作，如選擇、連接、聚集等。其中連接操作是應用較多且比較復雜的一種。

由于數據流上的連接查詢往往需要較高的實時性，因此要在內存中進行。但內存空間有限，無法將所有歷史數據保留下來進行處理，在這種情況下基于時間的滑動窗口技術是應用極為廣泛和有效的一種技術。數據流連接的算法主要有基于Nested-loop的算法和基于哈希的算法等，由于基于哈希的算法具有以較高的效率，因此應用較多。Annita?N.Wilschut?Peter和M.G.Apers提出了對稱哈希連接算法SHJ，它是基于哈希的數據流連接算法的基礎。應用SHJ算法處理數據流連接查詢時，首先基于時間滑動窗口在內存中分別為兩個數據源S-A，S-B各創建哈希表HashTable?A和HashTable?B。假設一個來自S-A的元組T_A到達，先使用T_A探測S-B對應的哈希表HashTable?B，并輸出連接結果,然后將元組插入本數據流應的哈希表HashTable?A中,并刪除本窗口中過期數據，來自S-B的元組T_B到達后的操作類似。在連接的過程中輸出連接結果的同時也在不斷的構建兩數據流基于哈希表結構的時間滑動窗口。其他的XJoin、MJoin算法都可以用來處理數據流連接問題，它們的核心思想與SHJ算法一致。

但隨著通信技術、互聯網的發展，數據流的類型和形式也更加多樣化，對于數據流連接查詢連接處理的要求也更加多樣化，這些數據流連接查詢算法并不能解決實際中的一些問題，如在某些實際的數據流連接查詢應用中，兩路數據流之間的元組之間存在一一對應的關系。如有兩路數據流，數據流A和數據流B分別記為Stream?A和Stream?B，分別稱之為S-A和S-B,數據流中的元組可以表示為Tuple<t,v>,其中t表示元組的時間戳，v表示元組的值。T_A表示S-A中元組，T_B表示S-B中的元組，W_A和W_B分別代表為兩個數據流建立的時間滑動窗口A和時間滑動窗口B，但利用SHJ等算法處理此類數據流連接查詢時存在以下問題：

1.SHJ等算中數據流數據流A某元組探測連接數據流數據流B中的元組成功后輸出結果，然而該元組還會參與到與數據流B中其他元組的連接操作中，會輸出重復的連接結果，這會造成輸出錯誤。

2.如圖1所示，每個元組到來后都執行一次向其對應的時間滑動窗口的探測操作，探測前都要對時間滑動窗口加鎖，探測完成都要對時間滑動窗口解鎖，這樣就會產生大量的加鎖、解鎖操作，效率低下。以數據流S-A為例，當某個元組T_A到來后首先會對W_B進行加鎖，探測W_B后釋放對W_B的鎖。若T_A在W_B中未找到匹配的元組，則對W_A加鎖并且將元組T_A插入W_A中，并刪除W_A中過期的元組，隨后釋放對W_A的鎖。這種情況下，每個元組到來后會執行兩次加鎖和解鎖的操作，開銷就極為可觀了。

因此這些數據流連接算法無法在此應用場景下輸出正確的結果，不能解決此類數據流連接查詢的問題。

發明內容

本發明所要解決的技術問題是針對現有技術的不足，提供一種基于時間滑動窗口的數據流點連接查詢方法，該方法可以大大減少操作過程中加鎖和解鎖的開銷，保證連接結果的正確的前提下大大提高了數據連接和數據清理的效率。

本發明解決上述技術問題的技術方案如下：基于時間滑動窗口的數據流點連接查詢方法，包括如下步驟：

步驟1：為數據流A和數據流B分別建立基于時間的滑動窗口，分別為時間滑動窗口A和時間滑動窗口B，進入步驟2；

步驟2：為數據流A和數據流B分別設定更新周期為ta和tb；

步驟3：處理數據流A則依次執行步驟4至步驟8，處理數據流B則依次執行步驟9至步驟13；所述步驟4至步驟8與步驟9至步驟13并行執行；