發(fā)布時(shí)間：2021-07-06 13:27

　　社交網(wǎng)絡(luò)、網(wǎng)頁(yè)鏈接、城市道路交通網(wǎng)和大規(guī)模集成電路等均可抽象為頂點(diǎn)和邊的數(shù)量在千萬級(jí)以上的大規(guī)模圖（數(shù)據(jù)）,對(duì)這類大規(guī)模圖的高效分析與計(jì)算需要在分布式平臺(tái)上進(jìn)行。然而,大規(guī)模圖均衡劃分是分布式處理圖數(shù)據(jù)的核心問題,優(yōu)良的大規(guī)模圖劃分結(jié)果可以充分利用集群資源、提升數(shù)據(jù)處理效率。已有許多研究者以線性規(guī)劃、多級(jí)劃分、啟發(fā)式等方法對(duì)大規(guī)模圖劃分問題進(jìn)行了研究,并提出了許多求解算法。但已有算法存在劃分效率低、未充分考慮圖結(jié)構(gòu)、劃分結(jié)果質(zhì)量差等問題。因此,對(duì)大規(guī)模圖劃分算法進(jìn)行研究與創(chuàng)新,使其能夠提升大規(guī)模圖數(shù)據(jù)處理任務(wù)的計(jì)算效率,在大數(shù)據(jù)分析領(lǐng)域具有極大的理論意義和應(yīng)用價(jià)值。論文選題來源于國(guó)家自然科學(xué)基金項(xiàng)目,作者針對(duì)已有算法缺陷,結(jié)合標(biāo)簽傳播機(jī)制、多目標(biāo)優(yōu)化和對(duì)大規(guī)模圖內(nèi)部結(jié)構(gòu)的研究創(chuàng)新提出了兩種新的大規(guī)模圖劃分算法,同時(shí),用所提出的算法優(yōu)化了Giraph圖處理框架中的圖劃分處理組件,使其圖處理框架的性能得到了較大的提升。本文主要工作內(nèi)容及創(chuàng)新如下:（1）針對(duì)傳統(tǒng)大規(guī)模圖劃分算法劃分效率低、劃分質(zhì)量差且未充分利用分布式平臺(tái)的問題,本文基于輕量級(jí)的標(biāo)簽傳播機(jī)制,創(chuàng)新提出了一種新的高效平衡大規(guī)模圖... 

【文章來源】：西安電子科技大學(xué)陜西省 211工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：84 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

常見大規(guī)模圖數(shù)據(jù)

析及數(shù)據(jù)挖掘任務(wù)已經(jīng)不可能，需要利用分布式平臺(tái)進(jìn)行處理。文獻(xiàn)模圖處理框架進(jìn)行了對(duì)比分析研究。下面本文對(duì)流行的、具有代表性的處理框架進(jìn)行總結(jié)與分析。2.1 PowerGraph圖數(shù)據(jù)處理框架werGraph[29]是嵌入在 GraphLab[30,31]中的底層圖處理框架。目前專門針據(jù)處理的框架 Pregel[32]不適合處理自然圖數(shù)據(jù)，問題在于高度頂點(diǎn)和分很差。設(shè)計(jì) PowerGraph 時(shí)就是為了應(yīng)對(duì)上述兩個(gè)問題，其中 Power 是布[22]的圖數(shù)據(jù)。PowerGraph主要貢獻(xiàn)有兩點(diǎn)：第一，提出了GAS(Gather)計(jì)算模型[33]，將高維度點(diǎn)并行化；第二，采用頂點(diǎn)切分，均衡集群負(fù)載 還有一些其它特性，包括 3 種執(zhí)行模式（全局同步，全局異步，可串行化量 Cache 特性，具體特點(diǎn)可以參看論文[29]。個(gè) PowerGraph 架構(gòu)如圖 2.1 所示。最上層是 PowerGraph 系統(tǒng)，它和 G一起，采用 C++實(shí)現(xiàn)，利用 HDFS 進(jìn)行數(shù)據(jù)輸入和輸出，利用檢查點(diǎn)實(shí)現(xiàn)

圖2.2 GraphX 整體結(jié)構(gòu)圖raphX 的圖數(shù)據(jù)存儲(chǔ)模式與劃分策略。GraphX 中圖數(shù)據(jù)的分布式存儲(chǔ)模，邊會(huì)被分配到每個(gè) EdgePartition，頂點(diǎn) Master會(huì)被分配到每個(gè)VertexPartition 會(huì)擁有本地邊關(guān)聯(lián)的頂點(diǎn)的 Ghost 副本。Ghost 副本數(shù)量和邊分都會(huì)受到劃分方法的影響，因此劃分策略的選取是非常的關(guān)鍵，最好是結(jié)構(gòu)來進(jìn)行選取。GraphX已有RandomVertexCut、Canonical- RandomVeartition1d、EdgePartition2d 四種劃分策略。于 GraphX 是基于 Spark 平臺(tái)并對(duì)其進(jìn)行擴(kuò)展，所以 GraphX 天然具有可擴(kuò)展性和執(zhí)行效率，并且 GraphX 的 Graph 和 Table 兩種視圖共享底可以降低計(jì)算和存儲(chǔ)的開銷。但是 GraphX 上的消息計(jì)算會(huì)同時(shí)訪問源點(diǎn)，所以其上的消息計(jì)算開銷較大，從而會(huì)影響圖數(shù)據(jù)計(jì)算效率。2.3 Giraph圖數(shù)據(jù)處理框架iraph[37]是一個(gè)迭代式的圖計(jì)算系統(tǒng)。雅虎開發(fā)了 Giraph，在開發(fā)時(shí)采取的 Pregel 模型[32]，Pregel 模型超步迭代的示例如圖 2.3 (a)所示。后來，

【參考文獻(xiàn)】：
期刊論文
[1]改進(jìn)的點(diǎn)到三角網(wǎng)距離快捷算法[J]. 吳耕宇,潘懋,郭艷軍,李兆亮.  計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2014(03)
[2]BHP:面向BSP模型的負(fù)載均衡Hash圖數(shù)據(jù)劃分[J]. 周爽,鮑玉斌,王志剛,冷芳玲,于戈,鄧超,郭磊濤.  計(jì)算機(jī)科學(xué)與探索. 2014(01)



本文編號(hào)：3268329