图作为计算机科学的一种基本的数据结构,可以用来描述存在多种关系的复杂数据,如社交网络,蛋白质交互网络,化学分子结构,交通网络等等。子图精确匹配是图数据库管理的一种基本操作,其概念是在数据图中查找出用户给定查询图的全部匹配,目前已经有大量关于子图精确匹配算法的研究成果,但是随着互联网技术的飞速发展,各个领域的数据量呈爆炸式增长,图数据的规模越来越大,导致其不可避免的存在噪声数据,而且子图精确匹配通常不能满足用户的模糊查找。基于这些因素,子图相似匹配作为子图精确匹配操作的一种延伸,具有重要的研究意义。子图相似匹配的概念是给定查询图q,数据图G,临界值θ,对于每一个查询图q至多缺少θ条边的查询子图p,在数据图查找出p的全部精确匹配。那么无论是精确匹配还是相似匹配,其基本内容仍然是子图同构问题,子图同构问题已经被证明是NP完全问题,为了提高查找效率,本文分别从构建索引和利用云计算环境两方面考虑,提出了两种子图相似匹配方法,分别为基于索引的子图相似匹配方法和基于云环境的子图相似匹配方法。在基于索引的子图相似匹配方法中,主要是利用混合邻居单元来对数据图的每个节点构造索引,并利用多个查询子图可共享一棵生成树的特点,来利用随机生成树集的剪枝能力来提高查找效率,另外,对查询图的所有查询子图,提出了一种类似频繁挖掘的深度优先的枚举顺序,以此来剪枝掉不匹配的子图。在基于云环境的子图相似匹配方法中,主要分四步来完成整个查找算法,首先对查询图松弛为符合θ约束的查询子图集,然后将这些查询子图集分解为更小的查询结构,即h树,然后在机器群中对h树集实现并行精确匹配操作,最后,将匹配结果进行连接来获得最后的查询结果。本文的最后会对基于索引的子图相似匹配方法与基于云环境的子图相似匹配方法做实验对比分析,分别利用真实数据集与合成数据集来验证在实现面向大图数据的子图相似匹配算法中,这两种方法的有效性与可扩展性。