作为数学的一个新的分支,图论起源于著名的哥尼斯堡七桥问题,它以图作为研究对象。近年来受计算机科学技术飞速发展地刺激,图论的发展极其迅速。其应用范围不断拓广,出现了越来越多的以图形建模的数据,例如化合物分子,蛋白质交互网络等。随着这些数据规模不断地增大,如何有效地管理和挖掘海量的图数据成为图数据库研究的核心问题。近年来,图数据库中的近似查询逐渐引起了越来越多的关注,但由于图数据自身结构的复杂性,如何从海量的图数据中迅速找到近似满足给定查询要求的答案成为一个挑战。针对这个问题,本文通过分析图的频繁结构和拓扑关系,定义了一种新的图相似性度量的标准,并在此基础上提出了一种有效的针对近似图包含搜索的索引构造方法,极大地提高了查询的效率。本文的研究成果主要有：(1)提出了一种新的衡量图相似性的标准。本文从图编辑距离的定义入手,进而研究图之间的拓扑关系,并给出了图之间近似程度的形式化表达。该表达为本文提出的近似查询算法提供了理论基础。(2)提出一种新的基于频繁子图的索引结构—倒排频繁子图索引,进一步将两个图之间的编辑距离计算拓展到整个数据库,以避免时间效率很差的顺序查找。(3)发现了利用频繁子图性质可以加速公共频繁子图的匹配过程。提出了分层倒排频繁子图索引(LIF-Index)的方法,使用分层关联结构组织频繁子图项的索引,形成基于频繁顶点的子图查询方法。实验表明,该方法有效地提高了子图的查询效率。(4)将过滤原理进一步应用到分层倒排频繁子图索引(LIF-Index)上,提出了一种高效的子图相似性查询算法,并与目前应用广泛的另外一种方法(gIndex)作了全面的比较。实验证明,本文提出的索引技术与建立在其上的子图近似查询算法具有良好的时间性能。