[發明專利]一種數據流等值連接優化方法、系統及電子設備

在審

• 申請號: 202010210265.X
• 申請日: 2020-03-23
• 公開（公告）號: CN111464451A
• 公開（公告）日: 2020-07-28
• 發明（設計）人: 熊超;范小朋;須成忠
• 申請（專利權）人: 中國科學院深圳先進技術研究院
• 主分類號: H04L12/801
• 分類號: H04L12/801;H04L12/815;G06F16/2455
• 代理公司: 深圳市科進知識產權代理事務所(普通合伙) 44316
• 代理人: 曹衛良

本申請涉及一種數據流等值連接優化方法、系統及電子設備。包括：利用漢明范數算法對接收到的多路數據流之間的獨立元素進行差異性計算；根據所述差異性計算結果計算所述多路數據流之間的交集，得到所述多路數據流需要等值連接的元素個數；根據所述元素個數確定等值連接順序，對所述多路數據流進行優化等值連接操作。本申請沒有窗口大小的限制，在連接的過程中，不會丟失元組數據，保證了結果的正確性；此外，本申請的算法空間復雜度為常數級，數據備份量小，并可在數據流動態變化的情況下使用。

技術領域

本申請屬于流數據處理技術領域，特別涉及一種數據流等值連接優化方法、系統及電子設備。

背景技術

Henzinger等人在1998年將數據流作為一種數據處理模型提出，他們將數據流定義為“只能按某種順序讀取一次的數據序列”。當前對數據流比較認可的定義為：所謂數據流S＝{a1,a2,……,ai}是指一個或多個設備源源不斷產生的數據，這些數據產生的速度隨著時間的變化而變化，同時，由于某些時間、存儲等因素的限制，數據只能按照某種順序讀取一次或幾次。

在大數據時代，信息來源豐富、種類多樣，但每種數據流可能只提供部分信息，結合多種來源的數據，獲取完整的信息成為勢在必行的趨勢。來自多個不同數據源的信息之間往往具有一定程度的關聯性，需要將多個數據源的信息進行整合得出全面的信息。在多路數據流等值連接中，具有關聯性的信息之間通過相同的連接屬性結合在一起，如同一個地區的不同種類的傳感器，可以將所處地區名稱作為等值連接屬性；對于執行等值連接操作而言，可以進一步優化等值連接謂詞執行的次序，減少等值連接操作執行的次數。

因此，等值連接的順序問題在數據流等值連接中十分重要。例如在中，可能比產生的中間結果少，執行效率高。

現有技術中，多路數據流連接優化的方案包括：

(1)ATR/CTR[Gu?X,Yu?P?S,Wang?H.Adaptive?Load?Diffusion?for?MultiwayWindowed?Stream?Joins.[C]//IEEE?International?Conference?on?DataEngineering.IEEE,2007.]：ATR/CTR是應對多個窗口數據流連接操作設計的自適應負載擴散算法。這兩個算法可實現保留語義的元組路由的功能，實現細粒度的負載均衡和連接操作的正確性。

(2)D-Streams[Zaharia?M,Das?T,Li?H,et?al.Discretized?Streams:Fault-Tolerant?Streaming?Computation?at?Scale[C]//Proceedings?of?the?Twenty-FourthACM?Symposium?on?Operating?Systems?Principles.ACM,2013.]將連續流分解為離散單元，并將它們作為Spark上的有序批處理作業進行處理。用于流連接的這種批處理只能提供近似結果，因為分離批次中的一些目標元組對可能彼此錯過以進行連接操作。

(3)TimeStream[Qian?Z,He?Y,Su?C,et?al.TimeStream:Reliable?streamcomputation?in?the?cloud[C]//Proceedings?of?the?8th?ACM?European?Conferenceon?Computer?Systems.ACM,2013.]設計的彈性替代和依賴追蹤機制，確保了數據流計算的可依賴性。