[發明專利]一種基于Pregel的分布式圖著色算法

在審

• 申請號: 201711241193.X
• 申請日: 2017-11-30
• 公開（公告）號: CN107992572A
• 公開（公告）日: 2018-05-04
• 發明（設計）人: 王鑫;甘瀛
• 申請（專利權）人: 天津大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06T11/00
• 代理公司: 天津市北洋有限責任專利代理事務所12201
• 代理人: 劉子文

技術領域

本發明涉及面向大規模圖數據的圖著色算法領域，具體為基于Pregel的分布式圖著色算法。

背景技術

近來，由于以RDF為代表的圖數據量日益增加，圖數據管理開始受到越來越多的關注。如何有效地對RDF圖數據進行加載、存儲和查詢成為現在研究的一個熱點問題。目前，已經有很多工作對如何有效管理RDF圖數據進行了研究，并提出了很多有效的解決方案。其中DB2RDF是一種將RDF圖存儲到關系數據庫的有效方法，但由于RDF圖數據規模的不斷增長，單機版本的DB2RDF的數據加載和存儲方案的性能受到限制，因此需要一種分布式的加載和存儲方案來提高已有方案的性能。同時，DB2RDF需要使用圖著色算法進行RDF圖存儲模式的構建，因此使用相對應的分布式圖著色算法來獲得可伸展的RDF圖數據裝載性能成為需要解決的問題。

圖著色問題是最著名的NP-完全問題之一，其的最簡單形式是頂點著色問題，即為圖中的每個頂點分配一個顏色，以保證任何相鄰的頂點不具有相同的顏色。圖著色算法可以應用于很多實際問題中，包括頻道分配問題、任務調度問題、安全裝箱問題等。

由于圖著色問題是NP-完全問題，目前沒有在多項式時間內解決這個問題的確定算法。但很多啟發式的單機或者分布式算法已經被提出，其中使用了貪心策略的啟發式算法是解決圖著色問題的最基本和經典的算法。由于現在需要處理的數據量越來越大，單機圖著色算法的性能漸漸不能滿足用戶的需要，因此，很多的并行圖著色算法被提出，這些算法通過分布式計算使得圖著色算法的效率進一步提高。然而，目前大多數分布式圖著色算法是基于傳統的共享內存模型，如MPI，OpenMP等。根據我們的調查，目前尚缺少相關研究工作對現有的分布式圖著色算法加以改進調整，適配到Pregel模型下進行算法研究與實驗比較。Pregel模型具有“以頂點為中心”計算的特點，因此更適合并行圖計算，使用Pregel消息傳遞模型來進行并行圖計算可以進一步提高圖計算效率。

目前已有的單機圖著色算法包括如下：

目前使用貪心策略的啟發式算法是解決圖著色問題最經典和有效的算法基于貪心策略的圖著色算法首先按照一定的順序尋找圖中的所有頂點，當尋找到某一頂點，為其分配可用的最小的顏色，即這個顏色不能與當前著色點的鄰居點的顏色相同。First Fit(FF)算法是一種簡單的貪心著色算法，它每次從一個隨機的頂點順序中得到下一個需要著色的頂點。Largest-Degree-First-Ordering(LFO)算法在尋找下一個著色頂點時總是選擇剩余頂點中度最大的點。Incidence-Degree-Ordering(IDO)算法則以鄰居中已著色的頂點的數量作為是否選擇的依據。Saturation-Degree-Ordering(SDO)算法選擇下一頂點時的依據則是其鄰居中顏色的數量。這些算法由于只適用于單機的情況，不能滿足大規模圖數據處理的要求，但它們仍然可以為設計圖著色并行算法版本提供借鑒和參考。

目前已有的并行圖著色算法包括如下：

并行啟發式圖著色算法都基于尋找獨立集的思想。其中，Lucy提出了一個并行構造獨立集的Maximal-Independent-Set(MIS)算法，其給每個頂點分配一個權重，這個權重來自一個從1到n的排序(n為頂點數量)，如果一個頂點具有本地最大的權重，即它的權重大于它的所有的鄰居頂點的權重，就把這個頂點加入到獨立集中，然后對獨立集中的頂點分配當前可用最小顏色。

Jones和Plassmann所提出的并行圖著色算法與MIS算法的不同是，給每個頂點分配一個不重復的隨機數作為權重和對每個獨立集中的頂點分配可用的最小顏色。Largest-Degree-First(LDF)算法將度最大的頂點首先放入獨立集，頂點的權值在相鄰點具有相同的度時用來解決沖突。Smallest-Degree-Last(SDL)算法分為兩個階段，第一階段根據頂點的度分配權重，第二階段通過所得的權重來尋找獨立集并著色。此外，Allwright等人對以上方法在SIMD和MIMD架構下進行了實驗對比。但這些方法都基于傳統的共享內存模型，而不能直接應用于Pregel消息傳遞模型。

Salihoglu等基于類Pregel模型對很多圖算法進行了優化，提出了幾種優化技術來提高類Pregel系統上圖計算的效率，并且其實驗顯示Pregel模型可以減少大規模圖數據并行計算的時間，Pregel模型以頂點計算為中心，計算由消息驅動，適用于分布式圖計算。

發明內容