图作为计算机学科中一种抽象的数据结构,具有很强的表达能力。现实生活中的很多错综复杂的关系都用图作为数据模型来描述,例如蛋白质交互网络,化学分子结构,社交网络等。但是这种超强的表达能力也导致了图数据上的各种算法难度大大增加。图上的很多问题是NP-完全问题。近些年随着信息技术以及计算机网络的飞速发展,尤其是互联网的日益普及,各个领域的数据量猛增,而从导致了图的规模也迅速扩充。如何在这样庞大规模的图中找到所需要的信息,一方面是迫切需要解决的实际问题,一方面解决这个问题又存在严峻的挑战。所以基于Web规模图数据查询成为了研究热点。子图匹配算法是图数据查询的一项基本操作,具有重要的研究价值。本文中子图匹配是指在单一Web规模图数据库中,通过子图同构找到所有匹配集合。它面临的主要问题就是子图同构问题。子图同构问题已经证明是NP完全问题,这就意味着查询效率低。为了提高查询效率,本文主要是从建立索引结构和分布式并行处理两个方面来考虑,并进行深入研究,分别提出了基于索引的子图匹配方法和基于云环境的子图匹配方法。在基于索引的子图匹配算法中,主要针对以往算法一次匹配一点的弊端进行改进,提出一次匹配一条路径的方法,从而建立了基于最短路径索引的子图匹配算法。主要是通过为Web规模图上的每个顶点邻居信息建立压缩结构来完成,这种结构是由顶点邻居组成的最短路径所构成。由于这种索引可以一次匹配一条路径,所以对Web规模图有很好的扩展性。在基于云计算环境子图匹配算法中,采用了基于内存云的分布式图数据处理系统,此分布式系统为用户提供了透明的接口,用户可以操作Web规模图仿佛它是存储在单台机器内存中。此方法考虑到分布式环境和数据更新延迟等因素会加剧索引维护的难度,所以放弃了建立索引来加快子图匹配的速度,而是采用图探测和并行技术弥补了缺乏索引所带来的性能上的下降。