面向图的分布式流计算关键技术研究

论文摘要

近年来,图数据作为能够清晰地揭示数据关联关系的数据结构,成为了一种非常有表现力的数据形式,在社交网络分析和用户画像等领域都有着广泛应用。同时随着数据规模的不断扩大以及在线计算的提出,图中经常包含上千万个顶点和边,难以完全存储在内存中,也难以实时返回计算结果,因而面向图的流算法和分布式算法研究逐渐成为了研究热点。局部拓扑结构计数是分析复杂网络的一项极为重要的任务,其中的图中三角形计数算法得到了广泛关注,然而研究点集中在研究单机上的近似计数流算法,以及分布式架构下的三角形精确计数算法,而关于图数据流的分布式三角形计数流算法并未得到深入的研究。针对此问题,本文改进了当前性能最好的三角形计数流算法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
• 表0-1 全文符号对照表
• 第一章 绪论
•   1.1 研究背景与意义
•   1.2 国内外研究现状
•     1.2.1 图计算框架相关研究
•     1.2.2 面向图数据的流算法相关研究
•     1.2.3 三角形计数算法研究
•   1.3 本文的主要工作
•   1.4 本论文的结构安排
• 第二章 相关技术与理论介绍
•   2.1 流数据处理简介
•     2.1.1 流数据处理的挑战
•     2.1.2 流数据处理常用技术
•   2.2 图数据流介绍
•     2.2.1 图模型相关概念简述
•     2.2.2 图数据流模型简述
•   2.3 MPI简介
•   2.4 本章小结
• 第三章 TRIèST-BASE算法的分布式研究
•   3.1 TRIèST-BASE算法简介
•     3.1.1 算法简介
•     3.1.2 算法理论分析
•   3.2 一种基于顶点哈希划分的分布式TRIèST-BASE算法
•     3.2.1 DVHT-b算法的基本思想
•     3.2.2 算法流程介绍
•     3.2.3 算法理论分析
•   3.3 本章小结
• 第四章 分布式的TRIèST-IMPR算法研究
•   4.1 TRIèST-IMPR算法简介
•     4.1.1 算法简介
•     4.1.2 算法理论分析
•   4.2 一种以固定概率实现边的映射的分布式TRIèST-IMPR算法
•     4.2.1 基本思想
•     4.2.2 算法流程
•     4.2.3 算法理论分析
•   4.3 一种基于顶点哈希值对比映射边的分布式TRIèST-IMPR算法
•     4.3.1 基本思想
•     4.3.2 算法流程
•     4.3.3 算法理论分析
•   4.4 本章小结
• 第五章 算法实现及实验结果分析
•   5.1 实验环境
•   5.2 实验数据集及评价标准
•     5.2.1 实验数据集
•     5.2.2 实验评价标准
•   5.3 实验设置与结果
•   5.4 本章小结
• 第六章 总结与展望
•   6.1 全文总结
•   6.2 展望
• 致谢
• 参考文献
• 攻读硕士学位期间取得的成果

文章来源

类型: 硕士论文

作者: 余梦笛

导师: 宋超

关键词: 图数据流,图计算,三角形计数算法,分布式流算法,近似算法

来源: 电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 电子科技大学

分类号: O157.5

总页数: 83

文件大小: 1619K

下载量: 51