基于圖的RDF數(shù)據(jù)流劃分算法研究.pdf

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

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

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