[發(fā)明專利]一種圖數(shù)據(jù)處理的方法、裝置及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201611081960.0
• 申請(qǐng)日: 2016-11-30
• 公開(kāi)（公告）號(hào): CN108132838B
• 公開(kāi)（公告）日: 2021-12-14
• 發(fā)明（設(shè)計(jì)）人: 夏應(yīng)龍;徐建;夏命榛
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50;G06F16/27
• 代理公司: 深圳市深佳知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44285
• 代理人: 王仲凱

1.一種圖數(shù)據(jù)處理的方法，其特征在于，包括：

主控節(jié)點(diǎn)獲取圖數(shù)據(jù)，所述圖數(shù)據(jù)包括M個(gè)頂點(diǎn)和多條有方向的邊，其中，每條邊連接所述M個(gè)頂點(diǎn)中的兩個(gè)頂點(diǎn)，且所述每條邊的方向由所述兩個(gè)頂點(diǎn)中的源頂點(diǎn)指向目的頂點(diǎn)，所述M為大于2的整數(shù)；

所述主控節(jié)點(diǎn)對(duì)所述圖數(shù)據(jù)進(jìn)行分割，以得到P個(gè)分片，其中，每個(gè)分片包括至少一個(gè)目標(biāo)頂點(diǎn)的入邊，所述入邊為指向所述目標(biāo)頂點(diǎn)的邊，所述P個(gè)分片對(duì)應(yīng)的目標(biāo)頂點(diǎn)數(shù)量之和等于所述M，且所述每個(gè)分片對(duì)應(yīng)的目標(biāo)頂點(diǎn)互不相同，所述P為大于1的正整數(shù)，所述P個(gè)分片包括第一分片和第二分片；

所述主控節(jié)點(diǎn)從所述每個(gè)分片中確定出至少兩個(gè)邊集合；

所述主控節(jié)點(diǎn)將所述第一分片所包含的至少兩個(gè)邊集合調(diào)度到至少兩個(gè)工作節(jié)點(diǎn)上以進(jìn)行處理；

所述主控節(jié)點(diǎn)將所述第二分片中包含的關(guān)聯(lián)邊集合調(diào)度到所述至少兩個(gè)工作節(jié)點(diǎn)上以進(jìn)行處理；所述關(guān)聯(lián)邊集合是包含所述第一分片對(duì)應(yīng)的目標(biāo)頂點(diǎn)的出邊的邊集合，所述出邊為從所述第一分片中的目標(biāo)頂點(diǎn)指出的邊。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述主控節(jié)點(diǎn)從所述每個(gè)分片中確定出至少兩個(gè)邊集合，包括：

所述主控節(jié)點(diǎn)將所述P個(gè)分片中邊的數(shù)值按照邊的方向填充到P行P列矩陣形式的數(shù)據(jù)結(jié)構(gòu)中，以得到P²個(gè)數(shù)據(jù)塊；

其中，每個(gè)數(shù)據(jù)塊為一個(gè)邊集合，所述每個(gè)分片包含至少兩個(gè)數(shù)據(jù)塊；所述P行P列矩陣是以所述M個(gè)頂點(diǎn)為橫軸和縱軸形成的，所述橫軸上的頂點(diǎn)為源頂點(diǎn)時(shí)，則所述縱軸上的頂點(diǎn)為目的頂點(diǎn)，或者所述橫軸上的頂點(diǎn)為目的頂點(diǎn)時(shí)，則所述縱軸上的頂點(diǎn)為源頂點(diǎn)。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述方法還包括：

所述主控節(jié)點(diǎn)為所述P²個(gè)數(shù)據(jù)塊中的每個(gè)數(shù)據(jù)塊設(shè)置一個(gè)唯一的塊標(biāo)識(shí)；

所述主控節(jié)點(diǎn)確定所述P²個(gè)數(shù)據(jù)塊的塊標(biāo)識(shí)與多個(gè)工作節(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系；

所述主控節(jié)點(diǎn)將所述第一分片所包含的至少兩個(gè)邊集合調(diào)度到所述至少兩個(gè)工作節(jié)點(diǎn)上以進(jìn)行處理，包括：

所述主控節(jié)點(diǎn)按照所述對(duì)應(yīng)關(guān)系，將所述第一分片包含的至少兩個(gè)數(shù)據(jù)塊，調(diào)度到所述至少兩個(gè)工作節(jié)點(diǎn)上以進(jìn)行處理。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述主控節(jié)點(diǎn)將所述第二分片中包含的關(guān)聯(lián)邊集合，調(diào)度到所述至少兩個(gè)工作節(jié)點(diǎn)上以進(jìn)行處理，包括：

所述主控節(jié)點(diǎn)按照所述對(duì)應(yīng)關(guān)系，將所述關(guān)聯(lián)邊集合對(duì)應(yīng)的數(shù)據(jù)塊調(diào)度到所述至少兩個(gè)工作節(jié)點(diǎn)上以進(jìn)行處理。

5.根據(jù)權(quán)利要求3或4所述的方法，其特征在于，所述方法還包括：

所述主控節(jié)點(diǎn)設(shè)置同步標(biāo)記；

所述同步標(biāo)記用于指示第一數(shù)據(jù)塊所在的工作節(jié)點(diǎn)在處理完所述第一數(shù)據(jù)塊之后與第二數(shù)據(jù)塊所在的工作節(jié)點(diǎn)進(jìn)行數(shù)據(jù)同步；其中，所述第一數(shù)據(jù)塊為所述第一分片中按照調(diào)度順序最后一個(gè)被調(diào)度的數(shù)據(jù)塊，所述第二數(shù)據(jù)塊為所述關(guān)聯(lián)邊集合對(duì)應(yīng)的數(shù)據(jù)塊中最后一個(gè)被調(diào)度的數(shù)據(jù)塊。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述主控節(jié)點(diǎn)從所述每個(gè)分片中確定出至少兩個(gè)邊集合，包括：

所述主控節(jié)點(diǎn)確定所述每個(gè)分片中目標(biāo)頂點(diǎn)的度數(shù)，所述度數(shù)表征所述目標(biāo)頂點(diǎn)與其他頂點(diǎn)關(guān)聯(lián)的緊密度；

當(dāng)?shù)谝荒繕?biāo)頂點(diǎn)的度數(shù)超過(guò)預(yù)設(shè)閾值時(shí)，所述主控節(jié)點(diǎn)將所述第一目標(biāo)頂點(diǎn)的入邊劃分到同一邊集合中。