本文關(guān)鍵詞：分布式大規(guī)模圖數(shù)據(jù)流式劃分算法FENNEL的改進(jìn)

  更多相關(guān)文章： 圖劃分 流式數(shù)據(jù) FENNEL 并發(fā)改進(jìn) 樹形網(wǎng)絡(luò)

【摘要】：圖劃分在分布式計算和大規(guī)模圖數(shù)據(jù)處理等方面有著重大的意義。當(dāng)圖數(shù)據(jù)規(guī)模較小時,靜態(tài)圖劃分算法(如METIS)能有效處理,獲得較小的切邊率;但是隨著應(yīng)用快速發(fā)展,圖數(shù)據(jù)規(guī)模的急劇增長給靜態(tài)圖劃分算法造成顯著挑戰(zhàn),因其處理速度及可擴(kuò)展性較差而難以處理千萬級以上大規(guī)模的流式圖數(shù)據(jù)。流式圖劃分算法的出現(xiàn)很好的解決了上述問題。FENNEL算法對多種流式圖劃分算法進(jìn)行了統(tǒng)一的建模,其切邊率要優(yōu)于目前主流的流式圖劃分算法,且較為接近學(xué)術(shù)界公認(rèn)優(yōu)秀的靜態(tài)圖劃分系統(tǒng)METIS,而其運(yùn)行速度卻比METIS快。不過,FENNEL算法是一種串行的流式劃分算法,擴(kuò)展能力受限,如何提高其并發(fā)性而且減少因并發(fā)性提高而帶來的切邊率影響就成為改進(jìn)所面臨的主要挑戰(zhàn)。本項研究通過對FENNEL的處理模型進(jìn)行分析,找出FENNEL現(xiàn)有分布式部署方法中,星形串行網(wǎng)絡(luò)模型存在的處理效率低、可擴(kuò)展性差等問題,并針對這兩方面的問題,提出了一種并發(fā)改進(jìn)方案,以及一種樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),并進(jìn)行理論推導(dǎo),以求證其可改善系統(tǒng)并發(fā)性及擴(kuò)展性。然后,對各種類型的圖數(shù)據(jù)進(jìn)行串行、并發(fā)模型的對比測試,測試數(shù)據(jù)表明了在原生圖數(shù)據(jù)以及圖數(shù)據(jù)隨機(jī)到達(dá)的情況下,FENNEL并發(fā)改進(jìn)方案可以保證幾乎不影響圖劃分切邊率,同時有效的加快圖劃分的速率,但是其速率會隨著工作節(jié)點數(shù)量的增加而減低;而樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能通過調(diào)整并發(fā)度來有效提高圖劃分速率,且其速率幾乎不會受到工作節(jié)點數(shù)量的影響。不過,對于按照廣度優(yōu)先搜索順序進(jìn)行預(yù)處理后的圖數(shù)據(jù),即圖節(jié)點按照鄰接關(guān)系順序進(jìn)行劃分處理,并發(fā)方法將顯著提高其切邊率。
【關(guān)鍵詞】：圖劃分 流式數(shù)據(jù) FENNEL 并發(fā)改進(jìn) 樹形網(wǎng)絡(luò)
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-8
• 1 緒論8-14
• 1.1 研究背景8-9
• 1.2 研究現(xiàn)狀9-12
• 1.3 本文的研究內(nèi)容12
• 1.4 本文的組織結(jié)構(gòu)12-14
• 2 FENNEL算法14-23
• 2.1 圖劃分相關(guān)定義和基本知識14
• 2.2 常見流式圖劃分算法14-16
• 2.3 流式圖劃分算法FENNEL16-21
• 2.4 FENNEL的分布式部署21-22
• 2.5 本章小結(jié)22-23
• 3 分布式FENNEL的改進(jìn)23-33
• 3.1 FENNEL的分布式模型23-25
• 3.2 頂點數(shù)據(jù)發(fā)送的并發(fā)改進(jìn)25-29
• 3.3 星形網(wǎng)絡(luò)到樹形網(wǎng)絡(luò)的改進(jìn)29-32
• 3.4 本章小結(jié)32-33
• 4 設(shè)計實現(xiàn)33-41
• 4.1 頂點數(shù)據(jù)發(fā)送的并發(fā)改進(jìn)設(shè)計實現(xiàn)33-37
• 4.2 樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的設(shè)計實現(xiàn)37-40
• 4.3 本章小結(jié)40-41
• 5 測試結(jié)果及分析41-52
• 5.1 星形網(wǎng)絡(luò)并發(fā)性改進(jìn)相關(guān)測試分析41-47
• 5.2 樹形網(wǎng)絡(luò)的相關(guān)測試與分析47-49
• 5.3 并發(fā)改進(jìn)對BFS圖數(shù)據(jù)劃分準(zhǔn)確性測試及分析49-51
• 5.4 本章小結(jié)51-52
• 6 總結(jié)與展望52-54
• 6.1 工作總結(jié)52
• 6.2 研究展望52-54
• 致謝54-55
• 參考文獻(xiàn)55-58

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 冷明平;孫凌宇;郭愷強(qiáng);邊計年;朱平;;賦權(quán)超圖劃分算法的電路劃分實驗比較研究[J];計算機(jī)工程與應(yīng)用;2012年16期

2 許金鳳;董一鴻;王詩懿;何賢芒;陳華輝;;大規(guī)模圖數(shù)據(jù)劃分算法綜述[J];電信科學(xué);2014年07期

3 李莉杰;陳端兵;王冠楠;;有向網(wǎng)絡(luò)重疊社區(qū)的快速劃分算法[J];計算機(jī)科學(xué);2014年S1期

4 盧風(fēng)順;宋君強(qiáng);張理論;張衛(wèi)民;任開軍;朱小謙;;面向全球數(shù)值天氣預(yù)報模式的加權(quán)等積并行數(shù)據(jù)劃分算法[J];計算機(jī)研究與發(fā)展;2012年04期

5 喻云峰;賴海濤;;一種基于隨機(jī)搜索的黑洞二劃分算法實現(xiàn)[J];科技廣場;2006年04期

6 李晨;葛聲;;一種重疊可信社團(tuán)劃分算法的設(shè)計與實現(xiàn)[J];微計算機(jī)信息;2011年09期

7 李孝偉;陳福才;劉力雄;;一種融合節(jié)點與鏈接屬性的社交網(wǎng)絡(luò)社區(qū)劃分算法[J];計算機(jī)應(yīng)用研究;2013年05期

8 牛建軍;劉上乾;韓寶君;任寶文;;同心圓檢測中的區(qū)域劃分算法[J];光子學(xué)報;2006年12期

9 呂德奎;;聚合算法在電力GIS中的應(yīng)用[J];電力信息化;2012年05期

10 王曉芳;賈宗維;;一種新的圖劃分算法在PPI網(wǎng)絡(luò)模塊化中的研究[J];山西農(nóng)業(yè)大學(xué)學(xué)報(自然科學(xué)版);2012年06期

中國重要會議論文全文數(shù)據(jù)庫 前4條

1 王玲娜;李興明;;基于最小支撐樹的通用區(qū)域劃分算法[A];2008年中國西部青年通信學(xué)術(shù)會議論文集[C];2008年

2 徐丹丹;章勇;;一種基于節(jié)點度更新的簇劃分算法[A];2008通信理論與技術(shù)新發(fā)展——第十三屆全國青年通信學(xué)術(shù)會議論文集（下）[C];2008年

3 劉培強(qiáng);謝青松;朱大銘;;用于基因表達(dá)譜數(shù)據(jù)聚類分析的貪心圖劃分算法研究[A];2006年全國理論計算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2006年

4 劉華偉;全慶一;;能量有效的基于連通度的分布式簇劃分算法[A];2011年全國通信安全學(xué)術(shù)會議論文集[C];2011年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 許金鳳;大規(guī)模動態(tài)自適應(yīng)圖劃分算法[D];寧波大學(xué);2015年

2 周爽;面向BSP模型的圖數(shù)據(jù)劃分算法的設(shè)計與實現(xiàn)[D];東北大學(xué);2013年

3 吳磊;復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法研究[D];太原理工大學(xué);2016年

4 宋俐;基于模糊聚類的社團(tuán)劃分算法研究[D];太原理工大學(xué);2016年

5 劉文杰;基于點分割的平衡圖劃分算法研究及其在Spark上的實現(xiàn)[D];蘭州大學(xué);2016年

6 吳迪;基于微博關(guān)注及轉(zhuǎn)發(fā)關(guān)系的社區(qū)劃分算法的改進(jìn)與實現(xiàn)[D];吉林大學(xué);2016年

7 滕躍;面向胚胎型仿生硬件的電路劃分算法研究[D];哈爾濱工業(yè)大學(xué);2016年

8 康曉慧;復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)劃分算法研究與實現(xiàn)[D];電子科技大學(xué);2016年

9 顧宏博;基于云聚合理論的社區(qū)劃分算法與應(yīng)用研究[D];南京郵電大學(xué);2016年

10 徐仁和;社交網(wǎng)絡(luò)的非重疊社團(tuán)劃分算法研究[D];重慶大學(xué);2016年

，

本文編號：911694