本文關鍵詞：基于點分割的平衡圖劃分算法研究及其在Spark上的實現(xiàn)

  更多相關文章： 大數(shù)據(jù) 圖劃分 分布式計算 Spark 點分割

【摘要】：近年來,隨著數(shù)據(jù)量的爆發(fā)式增長,相應地興起了對大數(shù)據(jù)處理平臺的研究熱潮,Hadoop的出現(xiàn)使人們從傳統(tǒng)的并行計算模型轉向對Mapreduce計算模型的研究。為了滿足數(shù)據(jù)挖掘和交互式實時查詢的計算需求,進一步提高數(shù)據(jù)處理能力和效率,UC berkeley大學高性能計算實驗室開發(fā)了Spark計算平臺,Spark引入了RDD(Resilient Distributed Datasets)數(shù)據(jù)模型,大大提高了交互式計算和迭代計算的計算速度,使得Spark成為大數(shù)據(jù)處理的利器。大數(shù)據(jù)的核心處理之一就是圖數(shù)據(jù)的處理,其中平衡圖劃分是圖數(shù)據(jù)處理的一個重要組成部分。眾所周知,平衡圖劃分是一個NP完全問題,應用非常廣泛,研究領域包括生物網絡,大規(guī)模集成電路設計,并行編程,負載均衡以及在線社交網絡分析等。傳統(tǒng)的圖劃分算法很多屬于全局算法,即算法執(zhí)行過程中需要遍歷全圖,過于依賴全圖知識,不適合對大規(guī)模圖數(shù)據(jù)的處理�；趯θ珗D訪問代價過大的考慮,2013年由Rahimian等人提出的一個去中心局部搜索算法JA-BE-JA,不需要進行中央?yún)f(xié)調,只通過局部知識來進行圖的劃分,極大的減少了集群中節(jié)點的通信開銷,大大提高了該算法的可擴展性和對大規(guī)模圖數(shù)據(jù)的處理能力。然而,JA-BE-JA算法仍然基于邊分割的設計思想,最近研究發(fā)現(xiàn)對于自然圖的處理,通過邊分割雖然保證了各子集中節(jié)點數(shù)的平衡,但是各個子集中邊的數(shù)量相差較大,同時該算法在多次迭代過程中容易陷入局部最優(yōu)解。于是本文提出了基于點分割的改進算法JA-BE-JA-VC(Vertex-Cut),新的算法采用了點分割的思想,子集的平衡性由每個分區(qū)中邊的個數(shù)來維持,而不是單純把節(jié)點數(shù)來作為平衡性的標準。新的算法在對自然圖劃分時,劃分產生的子集規(guī)模更加平衡。同時引入了模擬退火技術,增加了算法求解過程中的概率突跳性,避免陷入局部最優(yōu)陷阱。本文最后對算法進行了評估,結果表明新算法不僅能夠維持分區(qū)規(guī)模的平衡,同時對點的切分次數(shù)也相對較低,尤其對于服從冪律分布的現(xiàn)實數(shù)據(jù)進行處理時,基于點分割的算法設計思想具有很重要的借鑒意義。
【關鍵詞】：大數(shù)據(jù) 圖劃分 分布式計算 Spark 點分割
【學位授予單位】：蘭州大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP301.6
【目錄】：

• 中文摘要3-4
• Abstract4-8
• 第一章 緒論8-14
• 1.1 研究背景及意義8-10
• 1.2 國內外研究現(xiàn)狀10-12
• 1.3 論文的主要內容12
• 1.4 論文的組織結構12-14
• 第二章 相關理論技術14-33
• 2.1 圖劃分算法14-19
• 2.1.1 圖劃分的概念14-15
• 2.1.2 圖劃分算法分類15-19
• 2.2 Spark計算平臺19-33
• 2.2.1 簡介與組織架構20-21
• 2.2.2 彈性分布式數(shù)據(jù)集21-25
• 2.2.3 共享變量25-26
• 2.2.4 Spark編程接口26-29
• 2.2.5 工作原理29-31
• 2.2.6 Spark并行化技術31-33
• 第三章 JA-BE-JA算法及其改進33-45
• 3.1 JA-BE-JA算法33-36
• 3.1.1 JA-BE-JA基本思想33-34
• 3.1.2 交換節(jié)點選擇策略34-35
• 3.1.3 JA-BE-JA存在的不足35-36
• 3.2 JA-BE-JA局部最優(yōu)解的優(yōu)化改進36-37
• 3.3 基于點分割的JA-BE-JA算法37-40
• 3.4 算法并行化實現(xiàn)40-45
• 第四章 實驗與結果分析45-51
• 4.1 實驗環(huán)境45-46
• 4.2 實驗數(shù)據(jù)46
• 4.3 算法評估46-51
• 4.3.1 參數(shù)T和 δ 對算法的影響47-48
• 4.3.2 分區(qū)數(shù)k對算法的影響48-49
• 4.3.3 算法比較實驗49-51
• 第五章 總結與展望51-53
• 5.1 工作總結51
• 5.2 未來展望51-53
• 參考文獻53-57
• 研究生期間參與的項目57-58
• 致謝58

【相似文獻】

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

1 鄭麗麗;;圖劃分算法綜述[J];科技信息;2014年04期

2 英海燕;高級綜合中基于團劃分算法的資源分配[J];現(xiàn)代情報;2003年12期

3 蒿杰;彭思龍;;多級劃分算法的后處理與評價方法[J];小型微型計算機系統(tǒng);2010年01期

4 居繼龍，，李增瑞，李孝勖，任朗;時域有限差分方法中的網格非均勻劃分算法[J];北京廣播學院學報(自然科學版);1995年03期

5 肖儂，胡守仁，高洪奎，韓冰，宋輝;一個基于對象的程序劃分算法[J];電子學報;1997年05期

6 徐久強;崔行兵;于群;趙海;;基于子團規(guī)模的社團劃分算法與地理位置[J];東北大學學報(自然科學版);2012年11期

7 咼嘉妮,胡久鄉(xiāng),盧正鼎;有限元網格自動生成的并行區(qū)域劃分算法[J];華中理工大學學報;1999年07期

8 張魯峰,何連躍,李思昆;基于優(yōu)化合并準則的團劃分算法[J];電子學報;2001年08期

9 南國芳;李敏強;寇紀淞;;電路劃分算法改進[J];電子測量技術;2006年01期

10 孫雨耕，宋學軍，吳雪，許小滿;電網絡圖主劃分算法改進[J];天津大學學報;1995年05期

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

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

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

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

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

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

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

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

3 林慧嫻;個性化服務中用戶建模及社區(qū)劃分算法研究[D];南京郵電大學;2015年

4 吳磊;復雜網絡的社團劃分算法研究[D];太原理工大學;2016年

5 宋俐;基于模糊聚類的社團劃分算法研究[D];太原理工大學;2016年

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

7 馬靜;基于社交網絡的社團劃分算法研究[D];山東師范大學;2011年

8 韓明偉;超大規(guī)模集成電路劃分算法研究[D];西安電子科技大學;2008年

9 辛娟娟;社區(qū)劃分算法的研究與應用[D];北京林業(yè)大學;2015年

10 杜鵬飛;基于邊的相似性的復雜網絡社團劃分算法研究[D];山東師范大學;2014年

本文編號：549664