[發明專利]一種圖數據計算的方法、主機以及圖計算系統

有效

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

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

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

所述第一主機根據所述圖數據和所述計算結果集合，進行第X+1次的并發迭代計算，得到每個頂點上隨機游走實例的個數變為R₁/2個，所述R₁/2個隨機游走實例各自的當前路徑長度變為2L₁+1；

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

其中，第1次迭代計算為從磁盤獲取的數據進行迭代計算，其余次迭代計算為從磁盤獲取的數據進行迭代計算和從網絡獲取的數據進行迭代計算并發進行。

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

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

所述第一主機根據所述圖數據和所述計算結果集合，進行以頂點v為源點的第X+1次的并發迭代計算，得到每個頂點上隨機游走實例的個數變為R₁/2個，所述R₁/2個隨機游走實例各自的當前路徑長度變為2L₁+1，包括：

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

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

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

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

所述第一主機根據所述R₁個隨機游走實例各增加1個路徑長度，以及所述R₁/2個隨機游走實例各自的當前路徑長度變為2L₁，確定所述R₁/2個隨機游走實例各自的當前路徑長度變為2L₁+1。