[發(fā)明專利]一種圖數(shù)據(jù)計算的方法、主機以及圖計算系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201610527136.7
• 申請日: 2016-07-06
• 公開（公告）號: CN107590769B
• 公開（公告）日: 2021-02-09
• 發(fā)明（設(shè)計）人: 成杰峰;李震國;劉勤
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: G06T1/00
• 分類號: G06T1/00
• 代理公司: 深圳市深佳知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44285
• 代理人: 王仲凱

1.一種圖計算的方法，其特征在于，所述方法應(yīng)用于以磁盤為基礎(chǔ)的圖計算系統(tǒng)，所述圖計算系統(tǒng)包括M個主機，每個主機在本地磁盤上保存圖數(shù)據(jù)，所述圖數(shù)據(jù)包括N個頂點，每個主機同時運行N/M個不同源的路徑計算，每個頂點上當(dāng)前有R₁個隨機游走實例，每個隨機游走實例的當(dāng)前路徑長度為L₁，所述方法包括：

第一主機獲取頂點集合進行第X次迭代計算后的計算結(jié)果集合，所述頂點集合為所述第一主機進行第X+1次迭代計算時要執(zhí)行更新函數(shù)的頂點的集合；

所述第一主機根據(jù)所述圖數(shù)據(jù)和所述計算結(jié)果集合，進行第X+1次的并發(fā)迭代計算，得到每個頂點上隨機游走實例的個數(shù)變?yōu)镽₁/2個，所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁+1；

若所述R₁/2和2L₁+1滿足迭代完成條件，則所述第一主機完成所述圖數(shù)據(jù)的計算；

其中，第1次迭代計算為從磁盤獲取的數(shù)據(jù)進行迭代計算，其余次迭代計算為從磁盤獲取的數(shù)據(jù)進行迭代計算和從網(wǎng)絡(luò)獲取的數(shù)據(jù)進行迭代計算并發(fā)進行。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述第一主機獲取頂點集合進行第X次迭代計算后的計算結(jié)果集合，包括：

第一主機通過網(wǎng)絡(luò)獲取以頂點集合u_i完成的第X次迭代計算后的計算結(jié)果集合T_X(u_i)，所述頂點集合u_i中包括的頂點是所述第一主機進行以頂點v為源點的第X+1次迭代計算時要執(zhí)行更新函數(shù)的頂點，所述頂點v為所述第一主機上N/M個頂點中的其中一個，所述頂點集合u_i包括所述頂點v，X為大于0的整數(shù)；

所述第一主機根據(jù)所述圖數(shù)據(jù)和所述計算結(jié)果集合，進行以頂點v為源點的第X+1次的并發(fā)迭代計算，得到每個頂點上隨機游走實例的個數(shù)變?yōu)镽₁/2個，所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁+1，包括：

所述第一主機根據(jù)所述圖數(shù)據(jù)和所述計算結(jié)果T_X(u_i)，進行以頂點v為源點的第X+1次的并發(fā)迭代計算，得到所述以頂點v為源點上的隨機游走實例的個數(shù)變?yōu)镽₁/2個，所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁+1。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述第一主機根據(jù)所述圖數(shù)據(jù)和所述計算結(jié)果集合T_X(u_i)，進行以頂點v為源點的第X+1次的并發(fā)迭代計算，得到所述以頂點v為源點上的隨機游走實例的個數(shù)變?yōu)镽₁/2個，所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁+1，包括：

所述第一主機根據(jù)所述圖數(shù)據(jù)，進行以頂點v為源點的第X+1次的迭代計算，得到所述以頂點v為源點上的隨機游走實例的個數(shù)為所述R₁個，所述R₁個隨機游走實例各增加1個路徑長度；

所述第一主機根據(jù)所述計算結(jié)果集合T_X(u_i)，進行以頂點v為源點的第X+1次的迭代計算，得到所述以頂點v為源點上的隨機游走實例的個數(shù)變?yōu)镽₁/2個，所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁；

所述第一主機根據(jù)所述R₁個隨機游走實例各增加1個路徑長度，以及所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁，確定所述R₁/2個隨機游走實例各自的當(dāng)前路徑長度變?yōu)?L₁+1。