给定一张查询图和一张数据图,在数据图中查找与查询图同构的所有子图的算法称之为子图枚举算法。子图枚举算法是图分析基础算法之一,在生物化学、生态学和社交网络分析等领域中有着广泛的应用。随着计算技术的发展,数据图的规模急剧增长,传统的单机子图枚举算法已无法在可接受的范围内完成大规模数据图的子图枚举任务。针对这种情况,研究者提出了一些基于通用大数据计算框架的分布式子图枚举算法。已有研究表明,在现有的分布式子图枚举算法中,会产生大量的中间结果,导致大部分的执行时间花费在中间结果的网络通信上,使得整体的子图枚举处理时间开销过长,而CPU的计算时间反而较少。现有的分布式子图枚举算法对数据传输量进行优化以尽可能减少中间结果数目的同时,进一步采用建立索引的方式减少重复计算。但是这些优化手段依然展开了所有的中间结果,导致中间结果的数量随着数据图的增大而急剧膨胀。因此,现有的分布式子图枚举算法存在着不能处理复杂查询、中间结果数量膨胀过快等问题。在详细分析了现有工作的不足之后,结合当前较流行的分布式图计算编程模型Pregel,从中间结果的压缩传输角度入手,设计了一种高效、低数据传输量的分布式子图枚举算法PTSearch。本文的主要研究工作和贡献有以下几点:(1)研究设计了一种通用的分布式子图枚举算法PTSearch。PTSearch算法将分布式子图枚举问题分为查询分解、部分匹配结果查询以及部分匹配结果展开三大步骤。(2)查询分解处理中,本文研究提出了一种基于动态权重调整和贪心策略的查询分解算法,降低了 PTSearch算法的迭代轮数。(3)基于Pregel模型完成部分中间结果的查询步骤,本文研究提出了部分匹配结果的压缩数据表示Gptr。Gptr是本文的核心数据结构。在网络通信过程中,Gptr代替了大量的部分匹配结果,减少了中间结果的传输量。(4)本文研究提出了减少迭代轮数、Gptr的批量压缩表示、通过自同构信息和顶点度数信息提前剪枝等三大细节层面的优化措施。这些优化措施进一步地减少了中间结果的传输量。(5)在上述关键技术方法研究与算法实现基础上,在四个真实图数据集上对PTSearch算法进行了实验和性能评估。从数据传输量来看,本文提出的PTSearch算法的平均数据传输量是目前主流算法PSgL算法的0.1%,是TwinTwigJoin算法的30%。从整体性能方面来看,在PSgL、TwinTwigJoin算法由于中间结果过多导致运行失败或者运行时间较长的情况下,PTSearch算法依然能够在较短的时间内完成子图枚举计算。综上所述,本文从中间结果的压缩传输这个新的思路减少了分布式子图枚举计算过程的网络通信量,并取得了较好的性能。在2016年第二届全国高校云计算应用创新大赛大数据技能赛全国总决赛中,本文设计实现的PTSearch算法取得最佳性能,荣获技能赛一等奖。