随着信息社会的信息迅速增长,人们对数据的处理有了更高的要求。由于许多数据及其关系可以比较自然地表示成图,因而对图数据结构的研究逐渐引起人们的关注。图结构数据在分子生物学、化学化合物分析、基因工程、社会关系学等领域都具有重要应用价值。搜索问题是图结构数据中最为重要的一个研究课题;搜索效率决定了图结构数据的应用效果。　　本文围绕图结构数据搜索问题展开研究。首先,从多重索引出发研究图结构数据搜索问题;然后,在频繁子图挖掘算法中,提出了一种决策树来裁减子图同构次数;最后,针对搜索中的相似性搜索问题,研究相似性测量方法。取得成果如下:　　(1)提出一种根据频繁支持度进行迭代的图结构数据搜索算法。这种算法思想基于如下事实:索引数量和索引能力都会受到频繁支持度的影响。具体过程是利用FSG频繁子图生成算法在不同支持度下多次迭代,在每次迭代中裁剪图数据库的搜索空间和频繁子图的数量。实验表明,该算法达到了预定的提高搜索效率的目的。　　(2)提出了一种裁剪子图同构次数的频繁子图决策树。首先基于向下闭包性质对频繁子图构建频繁子图决策树,然后利用频繁子图决策树解决频繁子图生成算法中多次搜索数据库或候选集时进行子图同构次数多的问题,从而通过裁减频繁子图同构次数,提高了频繁子图挖掘算法的效率。另外,本文给出了构建频繁子图决策树的宽度优先子图同构法的算法实现。通过裁剪子图同构的数量提高了挖掘算法的效率,给出了一条提高频繁子图挖掘算法的新道路。　　(3)提出了一种结合拓扑子图与编辑距离的测量方法。这种方法先用拓扑公共子图进行结构性描述,然后利用编辑距离的细节描述能力对最大拓扑公共子图内部的相似性距离进行调整,从而有效地发挥了最大公共子图法和编辑距离法各自的优点,使得图之间的相似性衡量更加有效、精确。给出了该方法是度量标准的证明。并通过一个简单的例子说明了该方法比图的编辑距离测量方法和图的最大公共子图测量方法更为有效。