本文主要研究内容
作者余梦笛（2019）在《面向图的分布式流计算关键技术研究》一文中研究指出：近年来,图数据作为能够清晰地揭示数据关联关系的数据结构,成为了一种非常有表现力的数据形式,在社交网络分析和用户画像等领域都有着广泛应用。同时随着数据规模的不断扩大以及在线计算的提出,图中经常包含上千万个顶点和边,难以完全存储在内存中,也难以实时返回计算结果,因而面向图的流算法和分布式算法研究逐渐成为了研究热点。局部拓扑结构计数是分析复杂网络的一项极为重要的任务,其中的图中三角形计数算法得到了广泛关注,然而研究点集中在研究单机上的近似计数流算法,以及分布式架构下的三角形精确计数算法,而关于图数据流的分布式三角形计数流算法并未得到深入的研究。针对此问题,本文改进了当前性能最好的三角形计数流算法TRIèST,提出了三种分布式流算法以提升算法性能。主要利用分配策略划分了图数据流,使得各工作节点独立地估计子图数据流中的三角形个数。本文的主要贡献如下:1.基于对TRIèST-BASE的分析与研究,提出了分布式改进算法DVHT-b(Distributed Vertex Hashing TRIèST-BASE)。对图数据流中的边流,算法利用哈希函数将边的两个顶点编号映射为多机环境中的工作节点编号,从而通过比较两个映射值将边单播或多播至对应的工作节点中参与计算。同时通过计算每个三角形可以被计数的概率,得到最终的估计值,通过仔细的理论分析证明了算法实现了对图中三角形数量的无偏估计;2.基于对TRIèST-IMPR的分析和研究,提出了两种适用于多机环境的分布式改进算法——DEHT-i(Distributed Edge Hashing TRIèST-IMPR)和DVHT-i(Distributed Vertex Hashing TRIèST-IMPR)。DEHT-i利用哈希函数,通过预设的固定概率实现边与工作节点的映射,同时计算图流中每个三角形被计数的概率以估计图流中的三角形数量。DVHT-i利用哈希函数,通过比较顶点映射值将边单播或广播至各工作节点,并提出了分组分级聚合器的概念,快速有效地实现多工作节点估计值的聚合。理论分析证明了两种算法皆实现了对图数据流中三角形个数的无偏估计,且降低了估计算法的方差;3.实现了三种改进算法,并在各种真实世界的大规模图上进行了大量的实验,证明了本文提出的改进算法显著降低了现有单机流算法的估计误差。
Abstract
jin nian lai ,tu shu ju zuo wei neng gou qing xi de jie shi shu ju guan lian guan ji de shu ju jie gou ,cheng wei le yi chong fei chang you biao xian li de shu ju xing shi ,zai she jiao wang lao fen xi he yong hu hua xiang deng ling yu dou you zhao an fan ying yong 。tong shi sui zhao shu ju gui mo de bu duan kuo da yi ji zai xian ji suan de di chu ,tu zhong jing chang bao han shang qian mo ge ding dian he bian ,nan yi wan quan cun chu zai nei cun zhong ,ye nan yi shi shi fan hui ji suan jie guo ,yin er mian xiang tu de liu suan fa he fen bu shi suan fa yan jiu zhu jian cheng wei le yan jiu re dian 。ju bu ta pu jie gou ji shu shi fen xi fu za wang lao de yi xiang ji wei chong yao de ren wu ,ji zhong de tu zhong san jiao xing ji shu suan fa de dao le an fan guan zhu ,ran er yan jiu dian ji zhong zai yan jiu chan ji shang de jin shi ji shu liu suan fa ,yi ji fen bu shi jia gou xia de san jiao xing jing que ji shu suan fa ,er guan yu tu shu ju liu de fen bu shi san jiao xing ji shu liu suan fa bing wei de dao shen ru de yan jiu 。zhen dui ci wen ti ,ben wen gai jin le dang qian xing neng zui hao de san jiao xing ji shu liu suan fa TRIèST,di chu le san chong fen bu shi liu suan fa yi di sheng suan fa xing neng 。zhu yao li yong fen pei ce lve hua fen le tu shu ju liu ,shi de ge gong zuo jie dian du li de gu ji zi tu shu ju liu zhong de san jiao xing ge shu 。ben wen de zhu yao gong suo ru xia :1.ji yu dui TRIèST-BASEde fen xi yu yan jiu ,di chu le fen bu shi gai jin suan fa DVHT-b(Distributed Vertex Hashing TRIèST-BASE)。dui tu shu ju liu zhong de bian liu ,suan fa li yong ha xi han shu jiang bian de liang ge ding dian bian hao ying she wei duo ji huan jing zhong de gong zuo jie dian bian hao ,cong er tong guo bi jiao liang ge ying she zhi jiang bian chan bo huo duo bo zhi dui ying de gong zuo jie dian zhong can yu ji suan 。tong shi tong guo ji suan mei ge san jiao xing ke yi bei ji shu de gai lv ,de dao zui zhong de gu ji zhi ,tong guo zai xi de li lun fen xi zheng ming le suan fa shi xian le dui tu zhong san jiao xing shu liang de mo pian gu ji ;2.ji yu dui TRIèST-IMPRde fen xi he yan jiu ,di chu le liang chong kuo yong yu duo ji huan jing de fen bu shi gai jin suan fa ——DEHT-i(Distributed Edge Hashing TRIèST-IMPR)he DVHT-i(Distributed Vertex Hashing TRIèST-IMPR)。DEHT-ili yong ha xi han shu ,tong guo yu she de gu ding gai lv shi xian bian yu gong zuo jie dian de ying she ,tong shi ji suan tu liu zhong mei ge san jiao xing bei ji shu de gai lv yi gu ji tu liu zhong de san jiao xing shu liang 。DVHT-ili yong ha xi han shu ,tong guo bi jiao ding dian ying she zhi jiang bian chan bo huo an bo zhi ge gong zuo jie dian ,bing di chu le fen zu fen ji ju ge qi de gai nian ,kuai su you xiao de shi xian duo gong zuo jie dian gu ji zhi de ju ge 。li lun fen xi zheng ming le liang chong suan fa jie shi xian le dui tu shu ju liu zhong san jiao xing ge shu de mo pian gu ji ,ju jiang di le gu ji suan fa de fang cha ;3.shi xian le san chong gai jin suan fa ,bing zai ge chong zhen shi shi jie de da gui mo tu shang jin hang le da liang de shi yan ,zheng ming le ben wen di chu de gai jin suan fa xian zhe jiang di le xian you chan ji liu suan fa de gu ji wu cha 。
论文参考文献
论文详细介绍
论文作者分别是来自电子科技大学的余梦笛，发表于刊物电子科技大学2019-07-17论文，是一篇关于图数据流论文,图计算论文,三角形计数算法论文,分布式流算法论文,近似算法论文,电子科技大学2019-07-17论文的文章。本文可供学术参考使用，各位学者可以免费参考阅读下载，文章观点不代表本站观点，资料来自电子科技大学2019-07-17论文网站，若本站收录的文献无意侵犯了您的著作版权，请联系我们删除。
标签：图数据流论文; 图计算论文; 三角形计数算法论文; 分布式流算法论文; 近似算法论文; 电子科技大学2019-07-17论文;