[發(fā)明專利]一種基于子圖構建的磁盤圖處理方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201810838033.1
• 申請日: 2018-07-26
• 公開（公告）號: CN109254725B
• 公開（公告）日: 2020-05-19
• 發(fā)明（設計）人: 王芳;徐湘灝;馮丹;程永利;張永選
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智;曹葆青

1.一種基于子圖構建的磁盤圖處理方法，其特征在于，包括：

(1)將輸入圖的頂點劃分為P個不相交的頂點區(qū)間，對于每個頂點區(qū)間，分別創(chuàng)建一個入射邊塊結構和一個出射邊塊結構，以利用所述入射邊塊結構存儲對應頂點區(qū)間中頂點的入射邊，利用所述出射邊塊結構存儲對應頂點區(qū)間中頂點的出射邊，然后對所述輸入圖中的邊進行遍歷，根據每條邊的源頂點和目的頂點，將邊寫入相應的入射邊塊和出射邊塊，其中，P的取值需要確保每一個入射塊或出射塊的大小小于內存的容量；

(2)設定各頂點的初始化值并選定活躍頂點，開始進行迭代處理；

(3)按照劃分的頂點區(qū)間，加載當前頂點區(qū)間的頂點及當前頂點區(qū)間的入射邊塊和出射邊塊到內存中得到目標圖數據；

(4)將所述目標圖數據中的每條入射邊寫入該入射邊目的頂點的入射邊隊列，將每條出射邊寫入該出射邊源頂點的出射邊隊列，構建以頂點為中心的內存子圖；

(5)所述內存子圖中的每個頂點并發(fā)地從各自的入射邊讀取數據，并根據讀取的數據對頂點值進行更新；

(6)將被更新的頂點寫回磁盤，確保整體計算結果的一致性；

(7)判斷是否達到收斂條件，如果達到，執(zhí)行步驟(8)，否則進入下一次迭代，執(zhí)行步驟(3)；

(8)結束迭代圖計算，輸出計算結果。

2.根據權利要求1所述的方法，其特征在于，在所述入射邊塊結構中的邊按邊的目的頂點進行排序，在所述出射邊塊結構中的邊按邊的源頂點進行排序。

3.根據權利要求1所述的方法，其特征在于，所述活躍頂點為頂點值在上一輪迭代中被更新的頂點。

4.根據權利要求2所述的方法，其特征在于，所述將所述目標圖數據中的每條入射邊寫入該入射邊目的頂點的入射邊隊列，將每條出射邊寫入該出射邊源頂點的出射邊隊列，構建以頂點為中心的內存子圖，包括：

對于所述目標圖數據中的每條入射邊，首先訪問該入射邊的目的頂點的內存地址，然后將該入射邊添加到其目的頂點的入射邊隊列；

對于所述目標圖數據中的每條出射邊，首先訪問該出射邊的源頂點的內存地址，然后將該出射邊添加到其源頂點的出射邊隊列。

5.一種基于子圖構建的磁盤圖處理系統(tǒng)，其特征在于，包括：

雙向邊塊結構構建模塊，用于將輸入圖的頂點劃分為P個不相交的頂點區(qū)間，對于每個頂點區(qū)間，分別創(chuàng)建一個入射邊塊結構和一個出射邊塊結構，以利用所述入射邊塊結構存儲對應頂點區(qū)間中頂點的入射邊，利用所述出射邊塊結構存儲對應頂點區(qū)間中頂點的出射邊，然后對所述輸入圖中的邊進行遍歷，根據每條邊的源頂點和目的頂點，將邊寫入相應的入射邊塊和出射邊塊，其中，P的取值需要確保每一個入射塊或出射塊的大小小于內存的容量；

加載模塊，用于設定各頂點的初始化值并選定活躍頂點后，按照劃分的頂點區(qū)間，加載當前頂點區(qū)間的頂點及當前頂點區(qū)間的入射邊塊和出射邊塊到內存中得到目標圖數據；

內存子圖構建模塊，用于將所述目標圖數據中的每條入射邊寫入該入射邊目的頂點的入射邊隊列，將每條出射邊寫入該出射邊源頂點的出射邊隊列，構建以頂點為中心的內存子圖；

子圖更新模塊，用于將所述內存子圖中的每個頂點并發(fā)地從各自的入射邊讀取數據，并根據讀取的數據對頂點值進行更新，然后將被更新的頂點寫回磁盤，確保整體計算結果的一致性，判斷是否達到預設收斂條件，若沒有達到所述預設收斂條件，則執(zhí)行所述加載當前頂點區(qū)間的頂點及當前頂點區(qū)間的入射邊塊和出射邊塊到內存中得到目標圖數據，若達到所述預設收斂條件，則結束迭代圖計算。