论文部分内容阅读
给定一张大的数据图和一张小的模式图,子图枚举的任务是找到数据图中所有与模式图同构的子图。子图枚举是许多复杂图分析应用的基础。分布式大规模子图枚举算法数据通信开销大,计算复杂度极高,因此,研究大规模数据图上的高效子图枚举方法具有重要的学术意义和实际应用价值。现有的分布式子图枚举算法可以按深度优先、广度优先分为两类。基于深度优先搜索模式的算法,存在盲目复制数据图到各个节点的弊端。当数据图规模增大或模式图变复杂时,其数据复制量急剧增大,使其难以扩展到大规模数据图或复杂模式图上。而基于广度优先搜索模式的算法,将子图枚举问题转换为分布式多路join问题。这些算法在join的过程中需要shuffle大量中间匹配结果,而这些中间匹配结果的数量可能远远大于数据图本身的规模,导致算法并不高效。此外,部分算法还需要昂贵的开销来构建和维护额外的索引结构。针对现有算法的缺点,本文进行了以下研究工作:(1)研究提出了一种基于回溯的静态图分布式子图枚举算法框架BENU。BENU将子图枚举任务划分为一组可以并行执行的局部搜索任务,每个任务以数据图的一个顶点为中心点,根据基于回溯的执行计划来枚举模式图在数据图中的匹配。BENU采用了基于邻接表的存储和按需shuffle技术,只需按需查询枚举过程中涉及到的数据图边集,不需要shuffle任何中间匹配结果,也不需要构建任何额外的索引。(第三章)(2)研究提出了一种基于搜索的最优执行计划生成算法。基于搜索的最优执行计划生成算法通过一系列优化技术来降低执行计划的执行开销,同时使用开销估计模型,从所有合法执行计划中选出具有最低执行开销的最优执行计划。此外还提出了两种剪枝技术来缩小算法的搜索空间。(第三章)(3)研究实现了本地数据库缓存技术和任务分割优化技术。本地数据库缓存技术使用内存缓存来存储从分布式数据库中获取的邻接表,充分利用任务内和任务间局部性,显著降低通信开销。而任务分割优化技术通过将一个大的局部搜索任务拆分成多个子搜索任务,有效解决局部搜索任务的负载不均衡问题。(第三章)(4)研究实现了基于Streaming-BENU算法框架的动态图分布式持续子图枚举算法。在上述静态图方法基础上,针对动态数据图进行扩展,提出了一种Streaming-BENU算法框架,解决动态图上的持续子图枚举问题。Streaming-BENU通过枚举增量模式图的同构子图,可以直接从数据图的变化部分计算出匹配结果的变化情况,并在枚举过程中只保存动态数据图,不保存任何中间匹配结果。(第四章)(5)在真实的大规模图数据集上对BENU和Streaming-BENU算法框架进行了性能评估。实验结果表明,BENU和Streaming-BENU均优于现有最好的分布式(持续)子图枚举算法。尤其是在复杂模式图上,BENU和Streaming-BENU表现出了优异的性能。(第五章)