發(fā)布時(shí)間：2018-04-26 16:23

  本文選題：三角形枚舉 + 大規(guī)模圖數(shù)據(jù)　； 參考：《計(jì)算機(jī)應(yīng)用》2017年12期

【摘要】：經(jīng)典GT算法是三角形并行枚舉算法的MapReduce實(shí)現(xiàn),然而該算法只能枚舉全圖的三角形結(jié)構(gòu),對部分頂點(diǎn)構(gòu)成的三角形結(jié)構(gòu)無法直接進(jìn)行枚舉。針對此問題,提出一種直接枚舉部分頂點(diǎn)構(gòu)成三角形結(jié)構(gòu)的并行算法。首先,通過分析被選點(diǎn)的分布,給出被選點(diǎn)構(gòu)成三角形的所有組合集合;然后,通過對該集合的篩選,實(shí)現(xiàn)對部分點(diǎn)構(gòu)成三角形結(jié)構(gòu)的直接枚舉;最后,將該算法在Spark系統(tǒng)實(shí)現(xiàn),以實(shí)現(xiàn)該算法的高效性和廣泛性。在人工生成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上與GT算法進(jìn)行對比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,所提改進(jìn)算法的運(yùn)行時(shí)間只有GT算法運(yùn)行時(shí)間的1/3,在Spark上的運(yùn)行時(shí)間僅是Hadoop上運(yùn)行時(shí)間的1/7。該算法可用于更高效地直接生成圖中任意點(diǎn)所構(gòu)成的三角形數(shù)據(jù)集。
[Abstract]:The classical GT algorithm is the MapReduce implementation of triangle parallel enumeration algorithm . However , the algorithm can only enumerate the triangle structure of the whole graph , and the triangle structure composed of some vertices can not be enumerated directly . At last , by analyzing the distribution of the selected points , we present a direct enumeration of the triangle structure of the selected points . Finally , the algorithm is implemented in Spark system . The experimental results show that the running time of the proposed improved algorithm is only 1 / 7 of running time of the Hadoop . The algorithm can be used to directly generate the triangle data set of arbitrary points in the graph .

【作者單位】： 西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院;
【基金】：中國科技部國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1000703) 國家863重大項(xiàng)目(2015AA015307) 國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61332006);國家自然科學(xué)基金面上項(xiàng)目(61672432,61472321);國家自然科學(xué)基金青年項(xiàng)目(61502390)~~
【分類號】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 梁潘;;基于枚舉算法的優(yōu)化方法研究[J];重慶三峽學(xué)院學(xué)報(bào);2010年03期

2 曾立平,黃文奇;一種用于車間作業(yè)調(diào)度問題的智能枚舉算法[J];計(jì)算機(jī)工程與應(yīng)用;2004年30期

3 張景云;;改進(jìn)的堆的枚舉算法的研究[J];計(jì)算機(jī)應(yīng)用與軟件;2012年07期

4 葉志敏;;全部路徑之枚舉算法[J];揚(yáng)州師院學(xué)報(bào)(自然科學(xué)版);1988年04期

5 李六杏;;基于隱含條件挖掘的枚舉算法優(yōu)化[J];安徽科技學(xué)院學(xué)報(bào);2013年06期

6 郭廷花;;枚舉團(tuán)算法的改進(jìn)[J];山西煤炭管理干部學(xué)院學(xué)報(bào);2009年04期

7 劉運(yùn)龍;王建新;;3-維匹配問題的一種固定參數(shù)枚舉算法[J];計(jì)算機(jī)科學(xué);2010年05期

8 宋旭東;紀(jì)秀花;;穩(wěn)定婚姻匹配問題的一個(gè)快速枚舉算法[J];工程圖學(xué)學(xué)報(bào);2010年03期

9 杜慧江;孫強(qiáng);;一種生成所有堆的枚舉算法[J];計(jì)算機(jī)工程;2006年20期

10 賈曉峰;郭廷花;續(xù)曉欣;;關(guān)于最大團(tuán)問題的一種新算法[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

相關(guān)碩士學(xué)位論文 前5條

1 馮軒;基于Pregel模型的大規(guī)模分布式子圖枚舉算法研究與實(shí)現(xiàn)[D];南京大學(xué);2017年

2 杜慧江;基于子樹生成的堆枚舉算法[D];華東師范大學(xué);2006年

3 蘭娟;樹枚舉算法的設(shè)計(jì)與研究[D];華東師范大學(xué);2013年

4 丁小冬;最小—最大堆枚舉算法的研究[D];華東師范大學(xué);2010年

5 李言剛;左傾堆枚舉算法的研究[D];華東師范大學(xué);2010年

，

本文編號：1806769