随着图结构在复杂数据建模方面的广泛应用,图数据库技术得到了快速发展。如何从图数据库中快速检索数据已经成为一个研究热点。在图查询中,子图匹配查询和相似性查询是两种重要的查询方式。子图匹配查询是指返回数据库中包含查询图的图集合,而相似性查询是返回数据库中与查询图相似的图集合。处理子图匹配查询和相似性查询时,分别需要进行子图同构验证和图相似度计算,但子图同构验证和图相似度计算已经被证明是NP难题。为了快速有效地返回图查询的结果,目前主要采用“分类过滤+验证”两阶段处理机制。在这种机制中,首先预定义分类过滤规则,将图数据库分类,然后提取查询图特征,找到结果可能出现的类别,从而生成规模较小的候选集,最后对候选集进行子图同构验证或者图相似度计算得到最终的结果集。其中,人们可以根据分类过滤规则构造合适的图索引来提高查询效率。现有的用于处理子图匹配查询的图索引方法中,一般都是在查询前离线建立图索引,而忽视了查询图序列在时间上的相关性,容易出现冗余查询；已有的相似性查询的图索引方法主要集中在减少相似度的计算时间,而并没有提出一种缩小候选集规模的方法,仍需扫描整个数据库才能得到结果集。针对以上子图匹配查询问题,本文提出了一种双索引的方法。其主要思想是：首先采用传统方法,基于图数据库离线建立图索引DIndex(Database Index);然后在查询过程中,在线实时建立图索引HIndex(History Index)。HIndex中存放的是根据查询热度得到的一组频繁查询结构。这样当某些图被重复查询时,可以首先搜索HIndex,如果搜索成功,即可直接得到结果集,从而避免子图同构验证；如果搜索失败,则可按照传统方法搜索基于图数据库建立的索引DIndex,得到候选集。为了缩小相似性查询问题中候选图的规模,本文提出了一种多层过滤方法,并针对于不同的过滤层,分别提出了相适应的索引结构。首先将查询图的规模信息和顶点标签信息与图数据库中的图进行比较,将高偏差的图剔除；然后利用本文提出的基于子图向量异或乘积的计算方法得到一个有序集合,使得可能满足查询要求的图聚集在该集合的前半部分：之后本文采用类似二分查找的方式,通过计算映射距离,动态调整得到一个合适的下标值,使得可能满足要求的图都出现在该下标的左侧,这样就可以将该下标左侧的图直接加入到候选集；为了提高结果集的查全率,有序集合中出现在下标右侧的图也有一部分被选入候选集。最后,通过计算候选集中的图编辑距离,返回满足查询要求的图集合。最后,本文通过实验验证了双索引方法和多层过滤方法在子图匹配查询和图相似性查询中的有效性。在子图匹配查询的实验中,本文采用不同密度的查询序列进行查询,得到双索引方法和传统单索引方法以及无索引方法在不同情况下的平均子图同构次数。分析实验结果发现,随着查询密度的增大,双索引方法中子图同构验证的次数与已有的两种经典方法相比明显减少,从而提高了查询效率。在相似性查询实验中,本文分别从索引建立时间,索引大小以及索引性能以及查全率四个方面将多层过滤方法与已有的Closure-Tree方法进行对比。实验结果表明,多层过滤方法在索引建立时间、索引大小和查询时间上都优于Closure-Tree方法的同时,又能保持95%左右的查全率。