基于圖的RDF數據流劃分算法研究.pdf

1、近年來，大圖數據特別是數十億頂點規(guī)模的圖數據大量涌現，這一趨勢對圖數據管理領域提出了全新挑戰(zhàn)。圖的存儲方式直接決定了圖數據的訪問效率、圖查詢與挖掘的效率。如何采用合適的劃分方法處理大圖數據，并能高效的存儲和進行圖運算，成為大規(guī)模圖數據庫領域需要迫切解決的問題。
　　目前來看，大圖存儲的基本框架是分布式存儲。圖劃分理論與方法，為解決該問題提供了有效途徑。但是面對圖數據庫海量特點和分布式處理的日益復雜，現有的圖劃分模型和方法還存在一些

2、不足。本文針對這些問題進行了研究和實驗，設計了基于啟發(fā)策略的圖數據流劃分算法，能夠以較小的時間開銷獲得較理想的劃分結果。主要工作包括以下幾個方面:
　　首先，介紹了當前圖數據庫的發(fā)展狀況和圖數據分區(qū)的的研究背景及意義，分析了該領域在國內外的研究現狀，討論了幾類圖劃分模型的定義，并對目前圖劃分方法進行了總結和分析。主要包括:網格劃分方法，譜聚類劃分方法，啟發(fā)式劃分方法，多層劃分方法等。
　　其次，介紹了圖數據流所涉及的概念，定

3、義了圖數據流劃分的模型和分區(qū)啟發(fā)函數策略，給出了針對圖文件和RDF文件的圖數據流劃分算法和實現過程。
　　最后，通過對幾個真實RDF數據集的劃分實驗，并與METIS(—種多層次的圖劃分算法)方法和哈希分區(qū)方法做了實驗數據對比，驗證了圖數據流劃分算法的有效性。實驗結果表明，圖數據流啟發(fā)劃分算法相比傳統(tǒng)的哈希分區(qū)方法，能有效地減少邊割數量和通信交互，提高了圖算法的性能;相比METIS方法減少了分區(qū)處理函數的時間消耗，并能更好的適用于大