[發明專利]Spark-Streaming中間數據分區方法、裝置、計算機設備和存儲介質

有效

• 申請號: 201910438036.0
• 申請日: 2019-05-24
• 公開（公告）號: CN110263059B
• 公開（公告）日: 2021-05-11
• 發明（設計）人: 唐卓;付仲明;陳岑;陳建國;李肯立;李克勤;廖湘科
• 申請（專利權）人: 湖南大學
• 主分類號: G06F16/2455
• 分類號: G06F16/2455
• 代理公司: 廣州華進聯合專利商標代理有限公司 44224
• 代理人: 黃晶晶;黃曉慶

1.一種Spark-Streaming中間數據分區方法，其特征在于，包括：

獲取Spark-Streaming map任務輸出的中間數據中的多個元素；

基于蓄水池抽樣算法，對所述多個元素進行抽樣處理，得到抽樣處理后的元素集群；

通過時間序列預測方法對所述元素集群中元素對應的頻率權重進行更新，對更新后的元素集群中各元素按照預設元素順序進行排序，所述元素對應的頻率權重是指元素在所述元素集群中的出現頻率；

基于排序后的元素集群，通過動態規劃方法求解數據分區對應的邊界元素；

根據所述邊界元素對所述更新后的元素集群中的元素進行分區，以使分區處理后最大分區內的各個元素對應的頻率權重之和最小。

2.根據權利要求1所述的方法，其特征在于，所述基于蓄水池抽樣算法，對所述多個元素進行抽樣處理，得到抽樣處理后的元素集群，包括：

從單個所述map任務對應的元素中選取前K個元素，根據所述K個元素得到樣本數組；

基于累計分布函數對未被選取的元素進行處理，以確定跳過m個元素，將第K+m+1個元素替換所述樣本數組中的任意一個元素；

遍歷各個map任務對應的所有元素，得到抽樣處理后的元素集群。

3.根據權利要求2所述的方法，其特征在于，所述基于累計分布函數對未被選取的元素進行處理，以確定跳過m個元素，包括：

通過累計分布函數，對未被選取的元素基于概率計算公式計算跳過不同個元素對應的概率；

基于所述跳過不同個元素對應的概率，根據約束公式計算最小的整數m。

4.根據權利要求1所述的方法，其特征在于，所述通過時間序列預測方法對所述元素集群中元素對應的頻率權重進行更新，包括：

獲取當前時間序列元素對應的頻率權重以及當前時間序列抽樣元素對應的頻率權重；

根據所述當前時間序列元素對應的頻率權重以及所述當前時間序列抽樣元素對應的頻率權重，對所述元素集群中各個元素對應的頻率權重進行更新。

5.根據權利要求1所述的方法，其特征在于，所述基于排序后的元素集群，通過動態規劃方法求解數據分區對應的邊界元素，包括：

獲取設置的初始狀態以及最終狀態，其中，所述初始狀態為將排序后的元素集群中的預設第一數量元素分配至一個分區時，各元素的頻率權重之和，所述最終狀態為將預設第二數量元素分配至預設多個分區時，最大分區對應的元素的頻率權重之和最小；

基于所述初始狀態以及所述最終狀態，通過狀態轉移方程求取最大分區以及所述最大分區對應的最小頻率權重之和；

根據所述最大分區以及所述最大分區對應的最小頻率權重之和，得到數據分區對應的邊界元素。

6.一種Spark-Streaming中間數據分區裝置，其特征在于，所述裝置包括：

中間數據獲取模塊，用于獲取Spark-Streaming map任務輸出的中間數據中的多個元素；

抽樣處理模塊，用于基于蓄水池抽樣算法，對所述多個元素進行抽樣處理，得到抽樣處理后的元素集群；

權重更新模塊，用于通過時間序列預測方法對所述元素集群中元素對應的頻率權重進行更新，對更新后的元素集群中各元素按照預設元素順序進行排序，所述元素對應的頻率權重是指元素在所述元素集群中的出現頻率；

邊界求解模塊，用于基于排序后的元素集群，通過動態規劃方法求解數據分區對應的邊界元素；

分區模塊，用于根據所述邊界元素對所述更新后的元素集群中的元素進行分區，以使分區處理后最大分區內的各個元素對應的頻率權重之和最小。

7.根據權利要求6所述的裝置，其特征在于，所述抽樣處理模塊包括：

樣本數組獲取單元，用于從單個所述map任務對應的元素中選取前K個元素，根據所述K個元素得到樣本數組；

替換處理單元，用于基于累計分布函數對未被選取的元素進行處理，以確定跳過m個元素，將第K+m+1個元素替換所述樣本數組中的任意一個元素；

遍歷處理單元，用于遍歷各個map任務對應的所有元素，得到抽樣處理后的元素集群。