图是一种以顶点和边为基础形成的一种结构化数据表现形式,相比传统的数据库表形式,具有非常灵活的表达能力。近些年来,Twitter, Facebook,微博,微信等社交工具的出现,产生了超大规模的社交图数据。如何处理超大规模的图数据成为了非常关键的研究问题。子图匹配问题是图数据处理领域中的一个非常基础和重要的问题。图上的搜索,模式挖掘算法都必须基于快速的子图匹配算法。子图匹配问题是一个NP难问题,前人的研究工作中给出了一些纯算法的解法,这些方法难以处理十几万顶点以上规模的图数据。也有一些工作通过建立索引的方式来处理大规模的图数据,但是这些索引的规模都是图规模的超线性函数,在图规模达到上亿级别的社交图时,索引的存储代价过大,无法实现。分布式图数据库的出现使得存储和操作超大规模的图数据成为现实。本文的工作以微软亚洲研究院(MSRA)研究的分布式图数据库Trinity为底层图数据存储引擎,研究了超大规模图上的子图匹配问题,提出了一个使用线性索引,基于快速图搜索的剪枝技术和大规模并行计算技术的子图匹配算法,论证了算法的正确性,完备性和不重复性。实验表明我们的算法具有很好的响应时间和可扩展性,说明了在大规模图上进行快速子图匹配的可行性。