随着科学技术的飞速发展以及计算机的普及,产生了海量的数据。在网络、数学、生物、化学等领域,数据起着至关重要的作用。图是一种通用且具有广泛研究价值的数据结构,作为一种最直观的表达方式,越来越多的应用依赖于图数据进行表示。图数据的应用变得越来越广泛,其规模迅速增大,同时数据也变得更加多样化和复杂化,如何从海量的图数据中挖掘有效的信息成为研究的核心问题。近年来,我们可以发现在图数据库中存在噪音以及错误的图越来越多,因此学术界愈加关注如何在图数据库中进行相似性搜索,从而得到隐藏的信息。图相似性搜索对于深入研究图数据库起着强烈的推进作用。图编辑距离是一种用来确定图相似性最有效的措施,在模式识别、计算机视觉、生物信息等领域有着非常广泛的应用。图编辑距离作为一种度量两个图之间相似性的有效方法,是不精确图匹配的基础。不精确的图匹配已经成为模式分析领域的重要研究焦点之一,在现实生活中无处不在。当前已经验证了图编辑距离计算是一个NP问题,在通常情况下,图编辑距离计算在多项式时间内无法解决,计算起来十分复杂,浪费了大量的时间,效率低下,所以如何避免过多的图编辑距离计算成为了亟待解决的问题。为此,学术界提出了计算图编辑距离边界的算法,以此来提高计算效率。图编辑距离边界算法虽然可以减少计算量,提高效率,但仍有优化的空间。本文的主要内容如下:(1)简单介绍了几种与图编辑距离相关的算法及各自存在的优缺点。(2)结合现有的图编辑距离边界过滤算法,提出了两种新的方法,分别针对两种不同的情况,对图编辑距离边界过滤算法进行优化,从而进一步减少计算所消耗的时间。(3)建立概率索引图,利用概率索引图找到更好的中介图,进而提出快速收敛方法来解决图相似性问题,进一步减少不必要的图编辑距离计算,达到提高效率的目的。(4)最后验证本文提出的方法,通过在真实数据集与人工数据集上进行实验研究,从各个方面综合分析新方法。结果表明,这些方法具有良好的性能,同时通过实验结果也证实了使用我们提出的新方法来进行图相似性搜索的有效性和可行性。