关键词：
分布式系统
图挖掘
图划分
频繁子图挖掘
摘要：
图作为一种基本的数据结构,可以用来表达事物之间复杂的关系,被广泛应用到现实社会的诸多场景中。近年来,大规模图计算成为图研究中热门的研究课题。由于图数据规模的增加以及图计算任务具有迭代性的特点,传统的Map Reduce框架需要反复读写HDFS,难以支持高效的图计算任务。因此,学术界和工业界设计了多种不同的并行图计算平台,以提高大规模图计算的效率。然而,大规模图数据的并行挖掘框架面临着以下挑战:(1)图数据规模大、单遍扫描、实时性高。高效图计算面临的首要挑战是如何高效地对图数据进行划分以实现并行计算。为提高图划分效率,并行图计算平台普遍采用了流式图划分策略进行实时划分,然而这种实时划分策略在进行图划分时仅读取一次图信息,难以保证图分区的质量。(2)图数据存在幂律分布特征。现实世界的图数据通常存在少量的包含数百万邻居的高度数顶点,是幂律图划分中的难点。单一的图划分策略不能同时对高度数顶点和低度数顶点的划分进行优化,难以兼顾负载均衡和低通信开销。(3)图挖掘算法具有高阶复杂性。许多图挖掘算法需要从图中寻找特定的子结构,在迭代计算中需要依赖多阶邻居顶点的信息,其计算复杂度随子图规模呈指数级增长,传统的顶点式图计算模型很难支撑复杂图挖掘算法的高效计算。针对图挖掘中存在的上述性质和挑战,本文从数据并行和计算并行两个维度研究高效的图计算平台,对流式图划分建模、混合图划分算法、并行频繁子图挖掘框架三个关键问题开展研究,主要贡献与创新点如下:(1)基于组合优化的流式图划分方法。实时图划分仅扫描图结构一次,难以保证图划分的质量。为了提高实时图划分的质量,本文将流式图划分中的边划分问题建模成一个带约束的组合优化问题,基于组合优化的视角寻找完全图划分的最优解,并将其扩展到一般图的情况。本文提出的算法从理论角度对图划分问题进行建模,首次对生成的图分区给出了严格的副本率上界。对比经典的HDRF算法,本文提出的算法可以将流式图划分的时间降低三倍左右,同时划分质量的提升超过一倍。(2)面向幂律图的混合划分算法。现实幂律图中顶点的度数存在高度差异,单一策略在图划分时难以兼顾负载均衡和低通信开销。为了提高幂律图划分的质量,本文提出了一种面向幂律图的混合划分算法,使用平衡边划分模型解决了幂律图中高度数顶点划分质量差的挑战,并采用标签传播策略将低度数顶点划分到最近的邻居顶点所在的分区,从而在图分区中保留了幂律图的局部拓扑结构。在多个幂律图数据上的实验表明本文提出的图划分算法可以将图计算的效率提高两倍左右。(3)基于单机多核架构的并行频繁子图挖掘框架。频繁子图挖掘是一类典型的具有高阶复杂性的图挖掘问题,需要庞大的算力支撑。为了提高频繁子图挖掘的效率,本文设计实现了一种通用的单机并行计算框架Prefix FPM。Prefix FPM设计了前缀投影的数据结构,并提出了前缀投影的方法,实现了支持度的计算快速,降低了频繁子图挖掘的复杂度,从而提升了频繁子图挖掘的效率。同时Prefix FPM设计了基于任务的并行挖掘策略,可以充分利用机器的算力。此外,Prefix FPM将前缀投影的方法拓展成为一个解决频繁模式挖掘问题的通用思路,实现了频繁路径挖掘、频繁子树挖掘和闭合频繁模式挖掘算法。在多个公开数据集上的实验表明Prefix FPM将频繁子图挖掘的效率提升了两个数量级。(4)面向分布式架构的三阶段频繁子图挖掘框架。由于频繁子图挖掘过程会生成海量的中间结果,在分布式场景下存在严重的通信瓶颈。为了降低分布式频繁子图挖掘的通信开销,本文实现了一个分布式频繁子图挖掘框架Par Prefix FPM。Par Prefix FPM在上述基于前缀投影的挖掘框架的基础上,采用三阶段的频繁子图挖掘流程减少分布式挖掘的消息量,并实现了基于生产者-消费者模型的异步通信机制。在多个公开数据集上的实验表明Par Prefix FPM极大地降低了分布式频繁子图挖掘中因通信引起的计算延迟,可以为频繁子图挖掘算法提供良好的加速效果。
万方学位论文库
同方学位论文库
