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

有效

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

本發(fā)明公開了一種基于子圖構建的磁盤圖處理方法及系統(tǒng)，包括：將圖數(shù)據(jù)組織為雙向邊塊結構；開始迭代圖計算；加載圖數(shù)據(jù)到內存中；通過高效的子圖構建方法構建以頂點為中心的內存子圖；對子圖進行更新；將更新的圖數(shù)據(jù)寫回磁盤；判斷是否達到收斂條件；結束迭代圖計算。本發(fā)明提出的基于子圖構建的磁盤圖處理方法通過將子圖構建過程中需要訪問的頂點和邊連續(xù)地組織在一起，確保在子圖構建過程中內存訪問局部性得到充分利用，很好地解決了現(xiàn)在磁盤圖處理系統(tǒng)中的高子圖構建開銷問題，顯著的提升了系統(tǒng)的整體性能。

技術領域

本發(fā)明屬于計算機大數(shù)據(jù)處理技術領域，更具體地，涉及一種基于子圖構建的磁盤圖處理方法及系統(tǒng)。

背景技術

在當前大數(shù)據(jù)背景下，呈現(xiàn)出越來越多的對大規(guī)模圖數(shù)據(jù)進行分析、處理及挖掘的應用需求。近年來，基于磁盤的圖處理系統(tǒng)由于其成本低、可擴展性強等特點得到了廣泛的關注，例如卡內基梅隆大學的GraphChi、洛桑聯(lián)邦理工學院的X-Stream、清華大學的GridGraph等。這些磁盤圖處理將圖數(shù)據(jù)分為若干個子圖，并且每次從磁盤中加載和處理一個子圖。另外，這些系統(tǒng)大多采用以頂點為中心的計算模型，在處理每個子圖之前，需要在內存中構建以頂點為中心的子圖數(shù)據(jù)結構。這個子圖構建過程要求系統(tǒng)為子圖中的每個頂點添加入射邊和出射邊。然而，由于邊的源頂點或目的頂點不連續(xù)的存儲在內存中，構建子圖的過程通常會帶來很大的開銷。例如，GraphChi在執(zhí)行PageRank圖算法時，其子圖構建時間占到整個運行時間的60％，導致高子圖構建開銷的主要原因是子圖構建過程導致了大量的內存隨機讀寫。

發(fā)明內容

針對現(xiàn)有技術的以上缺陷或改進需求，本發(fā)明提供了一種基于子圖構建的磁盤圖處理方法及系統(tǒng)，由此解決現(xiàn)有磁盤圖處理系統(tǒng)中的高子圖構建開銷較大的技術問題。

為實現(xiàn)上述目的，按照本發(fā)明的一個方面，提供了一種基于子圖構建的磁盤圖處理方法，包括：

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

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

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

所述內存子圖中的每個頂點并發(fā)地從各自的入射邊讀取數(shù)據(jù)，并根據(jù)讀取的數(shù)據(jù)對頂點值進行更新，然后將被更新的頂點寫回磁盤。

優(yōu)選地，在所述入射邊塊結構中的邊按邊的目的頂點進行排序，在所述出射邊塊結構中的邊按邊的源頂點進行排序。

優(yōu)選地，所述活躍頂點為頂點值在上一輪迭代中被更新的頂點。

優(yōu)選地，所述將所述目標圖數(shù)據(jù)中的每條入射邊寫入該入射邊目的頂點的入射邊隊列，將每條出射邊寫入該出射邊源頂點的出射邊隊列，構建以頂點為中心的內存子圖，包括：

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

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

優(yōu)選地，所述將被更新的頂點寫回磁盤之后，所述方法還包括：