图是一种重要的数据结构,有着强大的信息表达能力,可以描述现实中诸多网络类型的问题。随着互联网中数据规模的增长,其形成的图结构越来越复杂,如何在大规模数据图中有效地进行图数据查询是当前关注的问题。子图同构算法是图数据查询的核心。子图同构问题被证明是一个NP完全问题,不存在多项式时间内的算法,为了能够在可接受时间内完成大规模数据图下的查询,理想的解决方案是设计高效算法同时提高处理平台的性能。提高子图同构查询算法的性能需要从索引策略、剪枝规则、候选集生成策略和匹配规则四个方面着手改进,以求算法从局部到整体效率的提高。针对上述问题,论文进行了以下工作。首先,论文研究并设计了一种基于顶点和邻域信息的索引VNIndex。该索引的主要原理是将数据图中所有顶点与其周围邻居顶点建立单独的联系,探测与邻居顶点形成的点边信息,将这些信息整理构建形成以自身顶点为核心的索引数据。该索引结构能够压缩图数据,实现在最小索引规模下有效地检索信息。其次,论文设计了一种基于VNIndex索引结构的精确子图同构查询算法VNQuery。剪枝方面,算法设计并应用了一种先期剪枝和匹配中剪枝相结合的剪枝策略,细化了剪枝规则,提高了剪枝效果;候选集生成方面,算法中设计并实现了一种改进的候选集生成策略和基于邻域扩展的顶点查找顺序,减少了候选集生成规模,加快了查找速度;顶点匹配方面,算法设计了一种改进的顶点匹配规则,使用四种合计七条匹配规则进行匹配顶点的确认,完成匹配的同时进行细粒度的剪枝。论文利用GraphX模型对图数据自动切分存储的特性,完成了算法基于Spark分布式平台的实现,并在两种数据集上进行实验。实验结果表明,在大型图数据集上,论文设计的VNQuery算法具有较好的执行效率。