分布式图处理若干算法与统一图处理编程框架研究

来源 :南京大学 | 被引量 : 0次 | 上传用户:yannini01
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
现实世界中的许多数据,例如社交网络、生物信息网络等,都可以采用离散数学中的图结构进行建模。随着信息技术的飞速发展,图数据的规模急速增长,用户对图数据分析的性能要求也日益增长,采用分布式计算技术处理大规模图数据变得势在必行。分布式图处理技术的相关研究可以分为算法研究以及编程框架与系统研究两大类。在算法研究方面,大规模图处理面临计算复杂度高、计算耗时长的难点问题。针对其中较困难的顶点相似度计算、全量子图枚举、增量子图枚举三个典型图处理问题,本文开展了基于任务并行计算模式的分布式图处理算法研究。在编程框架与系统研究方面,现有分布式图处理系统缺乏统一的图处理编程模型与编程框架,系统易用性低,存在用户学习成本高、程序迁移代价高的难点问题,阻碍了分布式图处理技术的应用普及。为此,本文进行了统一分布式图处理编程模型和系统平台的研究。论文主要工作和创新点包括:(1)研究提出了一种基于开销预估模型的阈值自适应分布式顶点相似度计算算法。针对顶点相似度计算问题,现有分布式算法存在只能在高阈值或低阈值区间高效运行的缺陷。为此,本文研究提出了基于开销预估模型的阈值自适应分布式顶点相似度计算算法VSIM。该算法采用任务并行的方式,为每一个顶点生成独立的相似度计算任务。每个任务根据执行开销预估模型,针对高、低阈值区间自适应选择最合适的执行模式。实验结果表明,VSIM算法能够在广阈值范围内高效运行,有效克服了现有分布式算法的缺陷,在大多数测试例下能显著缩短执行时间。(2)研究提出了一种基于回溯的分布式全量子图枚举算法。针对全量子图枚举问题,现有分布式全量子图枚举算法多通过分布式多路连接实现,但它们需要在连接过程中混洗(shuffle)中间匹配结果,带来高昂的网络通信开销。为此,本文提出了一种基于回溯的分布式全量子图枚举算法BatchBENU,将全量子图枚举任务分解为一系列可并行执行的局部搜索任务,每个局部搜索任务在基于回溯的执行计划指导下,在数据图的不同区域搜索模式图的同构子图。Batch-BENU采用按需混洗技术避免混洗中间匹配结果,并进一步配合本地缓存机制降低网络通信开销。实验结果表明,Batch-BENU算法相比现有分布式全量子图枚举算法CBF、Bi GJoin能获得明显的性能提升,同时具备近线性的节点可扩展性。(3)研究提出了一种基于匹配模式转换的分布式增量子图枚举算法。针对现有分布式算法存在内存使用量高、网络通信量大的缺陷,本文研究提出了一种基于匹配模式转换的分布式增量子图枚举算法Streaming-BENU。通过增量模式图的概念,Streaming-BENU算法首先将增量子图枚举问题转换为增量模式图的全量枚举问题,进而在每个时间步为受更新影响的顶点生成局部搜索任务。每个任务从更新边出发,遵循基于回溯的增量执行计划,搜索增量模式图的匹配结果。实验结果表明,Streaming-BENU算法的响应时间显著低于现有分布式算法Delta-BiGJoin。在较大数据规模、较小缓存容量的超参数配置下,Streaming-BENU算法可以取得近线性的节点可扩展性。(4)研究提出了一种统一分布式图处理编程模型,实现了跨平台统一分布式图处理编程计算框架。现有分布式图处理系统缺乏统一的图处理编程模型与编程框架,用户的学习成本高、程序迁移代价高,系统易用性低。为此,本文首先研究提出了一种统一分布式图处理编程模型Pregel X。该模型为用户屏蔽了不同分布式图处理编程模型的差异、隐藏了底层不同分布式图处理系统的技术细节,实现了编程接口与底层分布式计算框架的解耦,降低了用户的学习负担与程序的跨平台迁移代价。基于Pregel X编程模型,进一步研究实现了跨平台统一分布式图处理编程框架UniGPS。UniGPS采用基于进程间通信的执行环境隔离机制,使用户基于Python语言编写的分布式图处理程序能够跨平台地运行在多个主流分布式图处理系统之上。实验评估表明Uni GPS在具备高易用性的同时,能够支撑顶点相似度计算、子图枚举等图分析算法。Uni GPS所能处理的图数据规模显著高于单机Python图处理库NetworkX。在同样的图规模下,UniGPS的执行时间显著低于NetworkX。
其他文献
学位
学位
目的:白血病是人体血液系统的恶性肿瘤性疾病。可根据病情急缓和细胞的成熟程度将白血病分类为急性和慢性两类。急性白血病由于其发作急、快速进展,临床尚未有特效的治疗药物。因此,对急性白血病致病机制的研究,引起了学者们的广泛关注。急性白血病患者的骨髓中,异常的原始细胞及幼稚细胞在各种致癌因子的作用下,无限增殖,取代了原有的正常造血细胞,抑制人体的正常造血,并浸润淋巴结、肝、脾、睾丸和中枢神经系统(包括大脑
学位
学位
在学科教学中,学科特性是教学展开的逻辑起点,对学科特性的深入理解是实现有效教学的基础。实践中,由于忽视对中学英语学科跨文化性的理解,长期存在“重知识、轻文化”的困境,过度重视中学英语的工具性,使得中学英语教学失去了文化涵养,遮蔽了应有的育人价值。在全球化、多元化的时代背景下,发展学生的跨文化意识显得越来越重要,如何在中学英语教学中实现跨文化性成为教学改革与发展的重要课题。本论文旨在探究“中学英语学
职业教育与普通教育是两种不同教育类型,具有同等重要地位。中等职业教育在高中教育层次与普通高中教育并列,在职业教育体系中居于中等层次,肩负人的发展和经济发展双重功能。中等职业教育在为国家培养中等应用型专业和技术人才、传承技能技术、提高国民素质、促进就业、推动经济发展和完善教育体系结构等方面发挥了重要作用。在七十余年的发展历程中,中等职业教育的教育质量、招生规模、社会地位和产教关系几经起伏,当前在理论
学位
学位
学位