科技不断发展,各门学科与计算机领域的结合越来越紧密,图作为重要的数据结构,其应用范围不断拓广。蛋白质网络,社交网络以及电子商务网络等,都是以图进行建模的数据。随着互联网用户成倍的增加以及各门学科问题研究的深入,图数据规模逐渐增大,形成了复杂而又密集的大规模图结构,对海量图数据进行有效地管理和挖掘成为图数据研究的关键。近年来,在大规模图上进行子图查询的应用倍受关注,传统的子图查询方法适用于较小规模图的查询,如何优化大规模图结构的存储并高效的从海量图数据中查找出特定结构的子图成为当前研究的一项挑战。因此,本文利用索引查询的优势,提出了一种在图数据上建立特征索引的查询方法,线下提取结点特征,建立索引结构,线上进行索引遍历。基于这一索引,本文分别对星型结构和非星型结构两种查询模式进行研究,在非星型结构的子图查询中,定义了图的模式分解概念,并对中间解构建图模型,经过连接预处理后利用多连接方法计算最小代价确定连接顺序,得到最小规模候选集和尽可能小的查询结构,从而有效提高同构检测速度和查询效率。本文的研究成果主要有:(1)提出邻接点标数特征表的定义,将数据图结构转化为特征表的方式存储,结点的标签、度以及邻接点不同标签及其个数四项信息作为特征对数据图结点进行分类,根据分类原则将结点及对应的特征信息存储在特征表中。线下提取特征存储为特征表加快了索引的构建。(2)提出利用特征表构建邻接点双层索引Dulaq-Index的方法,根据特征表中结点的标签不同,每一类标签结点构建一棵特征索引树。根据特征表内特征间的包含关系分别设计上层索引和下层索引,根据邻接点标签个数是否唯一设计索引值,最终底层叶结点存储对应的数据图结点信息。实验表明该方法显著提高过滤效率,加速子图查询。(3)根据索引的特殊性,探究出星型结构子图的查询方法。提取星型查询图星心特征,通过遍历索引进行过滤得到结果集,再依赖存储结构的特殊性,对结果集展开得到最终查询结果。该查询算法极大提高了过滤能力并省略了对候选集的同构判别过程,与目前广泛应用的提取特征路径算法进行比较,有效缩短了子图查询时间。(4)针对非星型结构查询图的查询,提出结构的分解、子项过滤、中间解连接以及结果集同构判断的非星型图查询方法,定义了模式分解概念,提出基于图模型的中间解连接预处理方法,并结合MVP多连接查询算法,实现最小代价的中间解连接,得到的查询结果集是较小规模的图结构。再对结果集进行深度优先遍历得到最终的查询结果。实验证明该方法大大缩小查询图候选集,有效提高了查询效率。