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

有效

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

本發明實施例公開了一種圖計算的方法，用于提高圖計算的速率，節省時間。本發明實施例方法包括：第一主機獲取頂點集合進行第X次迭代計算后的計算結果集合，所述頂點集合為所述第一主機進行第X+1次迭代計算時要執行更新函數的頂點的集合；所述第一主機根據所述圖數據和所述計算結果集合，進行第X+1次的并發迭代計算，得到每個頂點上隨機游走實例的個數變為R₁/2個，所述R₁/2個隨機游走實例各自的當前路徑長度變為2L₁+1；若所述R₁/2和2L₁+1滿足迭代完成條件，則所述第一主機完成所述圖數據的計算。

技術領域

本發明涉及計算機領域，尤其涉及一種圖數據計算的方法、主機以及圖計算系統。

背景技術

隨著收集與產生數據的能力的進步，我們進入了大數據時代，每天我們都能從各類傳感器、設備和互聯網中收集到大量的數據。為了尋找新的商業價值和建立新的商業模型，我們必須處理、分析、存儲并理解這些大數據。隨著大規模圖數據分析的需要，近幾年涌現出了很多基于分布式或單機的并行圖計算系統，其中常見的有：大規模圖分布式計算框架(Pregel)、基于內存的分布式圖計算系統(GraphLab)、基于磁盤的單機圖計算系統(GraphChi)等。

“圖計算”是以“圖論”為基礎的對現實世界的一種“圖”結構的抽象表達，以及在這種數據結構上的計算模式。圖計算系統對所有的算法的運行都是以多輪迭代進行直到算法收斂結束。一般通過使用“以頂點想(think like a vertex)”的思路去抽象數據處理的算法，通過編寫頂點程序形成圖上的更新函數，其中，更新函數是由用戶定義的。在現有技術中，更新函數是用戶定義的可以處理一個源路徑的計算。一個更新函數可以修改一個頂點以及與它相連的邊上的權值。在圖計算完成一個算法的多次迭代中，每次迭代就是系統完成一遍在圖的每一個頂點上執行更新函數。

但在大數據分析的背景下，我們要處理的圖的大小通常是大于一臺計算機的內存。因此，在圖計算時，要根據集群中計算節點的數目把圖分成同等份數，并分配到這些計算節點的內存中，才開始計算。圖計算過程中需要各主機通過網絡不斷彼此通信告訴對方自己內存中的計算狀態才能使得整體的計算向前進行。一般采用基于隨機游走(randomwalk)的圖計算方法。其中，一個圖包括N個節點，對圖中的N個節點，我們需要獨立地從每個節點出發搜索一條以該節點為源點的隨機游走路徑，那么對同一個圖需進行N次圖計算。每次隨機游走都從圖中每個不同的起始節點開始，每一步隨機選取當前節點的一個相鄰頂點前進。其中，隨機游走往下一個相鄰頂點前進的每一步都需要圖計算的一次迭代，隨即游走路徑需要被采樣多長，系統就處理多少步迭代完成該次采樣。所以，N次采樣就運行N次圖計算，每次圖計算對應一次采樣計算，其總的計算時間就是一次分布式采樣計算時間的N倍。也可以擴展現有單機系統到多個不同的主機上同時運行這N次采樣，這樣整體的計算時間就是一次單機采樣計算時間的N/M倍，M為主機的個數。

但是，由于圖計算系統要處理的圖數據的N都很大，N是一個是變量，M很小，是恒量。所以，據上述分析，就算現有的圖計算系統快到能一秒鐘完成一次采樣計算，常見的超過千萬節點的圖就已經需要花超過10^7(10的7次方)秒的時間，即115天。因此，怎么降低圖計算的時間是一個重要的挑戰。

發明內容

本發明實施例提供了一種圖計算的方法、主機以及圖計算系統，用于提高圖計算的效率，節約時間。

本發明實施例第一方面提供一種圖計算的方法，該方法應用于以磁盤為基礎的圖計算系統，該圖計算系統包括M個主機，每個主機在本地磁盤上保存圖數據，該圖數據包括N個頂點，每個主機同時運行N/M個不同源的路徑計算，每個頂點上當前有R₁個隨機游走實例，每個隨機游走實例的當前路徑長度為L₁，該方法可包括：