基于Pregel模型的分布式圖著色算法*

甘 瀛，王 鑫+，馮志勇，楊雅君

1.天津大學 計算機科學與技術學院，天津 300354

2.天津市認知計算與應用重點實驗室，天津 300354

3.天津大學 軟件學院，天津 300354

1 引言

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

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

由于圖著色問題是NP-完全問題，目前沒有在多項式時間內解決這個問題的確定算法。但很多啟發式的單機或者分布式算法已經被提出，其中使用了貪心策略的啟發式算法是解決圖著色問題的最基本和經典的算法。現在需要處理的數據量越來越大，單機圖著色算法的性能漸漸不能滿足用戶的需要，因此很多的并行圖著色算法被提出，這些算法通過分布式計算使得圖著色算法的效率進一步提高。……