[發明專利]一種分布式的圖數據序列采樣方法及裝置

有效

• 申請號: 201910313368.6
• 申請日: 2019-04-18
• 公開（公告）號: CN110019253B
• 公開（公告）日: 2021-10-12
• 發明（設計）人: 張熙;雷鳴濤;楊金翠;方濱興
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 北京柏杉松知識產權代理事務所(普通合伙) 11413
• 代理人: 丁蕓;馬敬

本發明實施例提供了一種分布式的圖數據序列采樣方法及裝置，應用于分布式的計算節點，所述分布式的計算節點包括：兩個以上計算節點，其中所述方法包括：獲取預設的圖數據、采樣次數及采樣路徑長度；將所述采樣次數均分，得到每個計算節點各自的采樣次數，作為采樣分配次數；從每個計算節點處理的路徑集合中，按照所述采樣路徑長度，確定出路徑長度與所述采樣路徑長度的數值相同的目標路徑，所述目標路徑是由邊數量與所述采樣路徑長度的數值相同的所述圖數據的邊形成的，所述圖數據的每條邊包括至少一個元素；對每個計算節點的目標路徑，基于預先確定的權重，分別從形成該目標路徑的每條邊包括的至少一個元素中抽取一個元素，得到采樣元素序列。

技術領域

本發明涉及涉及數據分析技術領域，特別是涉及一種分布式的圖數據序列采樣方法及裝置。

背景技術

隨著通信技術的發展，形成了大量的數據，如何從大量數據中獲取有價值的信息成為人們所關注的問題。圖數據作為一種數據，目前相關技術中采用單個計算節點進行圖數據序列采樣，雖然單個計算節點實現了圖數據序列采樣，但是通過單個計算節點完成整個采樣過程，采樣效率較低。

發明內容

本發明實施例的目的在于提供一種分布式的圖數據序列采樣方法及裝置，用以解決現有技術中通過單個計算節點完成整個采樣過程，采樣效率較低的技術問題。具體技術方案如下：

第一方面，本發明實施提供了一種分布式的圖數據序列采樣方法，應用于分布式的計算節點，所述分布式的計算節點包括：兩個以上計算節點，所述方法包括：

獲取預設的圖數據、采樣次數及采樣路徑長度；

將所述采樣次數均分，得到每個計算節點各自的采樣次數，作為采樣分配次數；

從每個計算節點處理的路徑集合中，按照所述采樣路徑長度，確定出路徑長度與所述采樣路徑長度的數值相同的目標路徑，所述目標路徑是由邊數量與所述采樣路徑長度的數值相同的所述圖數據的邊形成的，所述圖數據的每條邊包括至少一個元素；

對每個計算節點的目標路徑，基于預先確定的權重，分別從形成該目標路徑的每條邊包括的至少一個元素中抽取一個元素，得到采樣元素序列，所述權重用于指示所述采樣元素序列在全量采樣元素序列集合中所占的比重，所述全量采樣元素序列集合中的全量采樣元素序列是按照所述采樣分配次數由所述分布式的計算節點各自采樣獲得的。

進一步的，在所述從每個計算節點處理的路徑集合中，按照所述采樣路徑長度，確定出路徑長度與所述采樣路徑長度的數值相同的目標路徑之前，所述方法還包括：

按照所述分布式的計算節點的數量，將所述圖數據的邊集進行分塊，得到多個分塊邊集；

將一個分塊邊集分配給一個計算節點；

確定每個分塊邊集中邊形成的各個路徑；

由每個分塊邊集形成的各個路徑，組成每個計算節點處理的路徑集合；

所述從每個計算節點處理的路徑集合中，按照所述采樣路徑長度，確定出路徑長度與所述采樣路徑長度的數值相同的目標路徑，包括：

基于每個計算節點處理的路徑集合，以該計算節點所分配的分塊邊集中的起始邊為起點，沿該分塊邊集中的起始點存在其余邊的方向，拓展查找到所述采樣路徑長度的數值減一條除所述起始邊以外的其他邊；

將該分塊邊集中沿起始邊拓展查找到，邊數量與采樣路徑長度的數值相同的所有邊，形成所述目標路徑。

進一步的，采用如下步驟確定權重：

針對每個計算節點，將形成該計算節點的所述目標路徑的所有邊上全量采樣元素序列的總數，與該計算節點包括的所有目標路徑的總數之積，確定為所述權重。