[發(fā)明專利]一種分布式的圖數(shù)據(jù)序列采樣方法及裝置

有效

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

1.一種分布式的圖數(shù)據(jù)序列采樣方法，其特征在于，應(yīng)用于分布式的計算節(jié)點，所述分布式的計算節(jié)點包括：兩個以上計算節(jié)點，所述方法包括：

獲取預設(shè)的圖數(shù)據(jù)、采樣次數(shù)及采樣路徑長度；

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

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

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

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

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

將一個分塊邊集分配給一個計算節(jié)點；

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

由每個分塊邊集形成的各個路徑，組成每個計算節(jié)點處理的路徑集合。

2.如權(quán)利要求1所述的方法，其特征在于，所述從每個計算節(jié)點處理的路徑集合中，按照所述采樣路徑長度，確定出路徑長度與所述采樣路徑長度的數(shù)值相同的目標路徑，包括：

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

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

3.如權(quán)利要求1所述的方法，其特征在于，采用如下步驟確定權(quán)重：

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

4.如權(quán)利要求1或3所述的方法，其特征在于，所述對每個計算節(jié)點的目標路徑，基于預先確定的權(quán)重，分別從形成該目標路徑的每條邊包括的至少一個元素中抽取一個元素，包括：

針對每個計算節(jié)點，將該計算節(jié)點包括的所有目標路徑的總數(shù)的倒數(shù)，確定為該目標路徑出現(xiàn)在每個計算節(jié)點中所有目標路徑的總數(shù)的出現(xiàn)概率；

針對每個計算節(jié)點的目標路徑，基于所述出現(xiàn)概率，與該目標路徑上第k個位置處的邊上元素總和的倒數(shù)，確定為該目標路徑中第k個位置處的邊的元素抽樣概率，其中，k遍歷取{k|0≤k≤L}中的各個非負整數(shù)值，L為采樣路徑長度；

按照所述元素抽樣概率，從所述第k個位置處的邊包括的至少一個元素抽取一個元素。