一种有效的图索引查询算法

Effective Graph Index Query Processing Algorithm

图是一种很强大的工具,在许多应用领域如化学化合物,生物信息,XML文档,图像处理和社会网络等应用中它可以表示其对象及它们之间的关系,而且在模式化复杂的结构数据时图发挥了越来越重要的作用.图的一个最基本的操作是图的查询处理,经典的图查询问题是给出图数据库和一个查询图,从图数据库中找出那些包含查询图作为子图的图.在本文中对于给定的查询图提出了一种有效的索引策略,在图数据库中选取具有判别力的树作为特征树,对这些特征树进行编码,将结构之间的比较转化为编码序列之间的比较,并利用特征树建立索引,提出了两种剪枝策略,过滤掉数据库中与查询图不是精确匹配的图.实验验证了所提出查询处理算法的有用性和有效性.

Graph is a very powerful tools, It can express object and the relations between them in various application areas, and graph played more and more important role in modelling complicated structure such as Chemical Compounds, Biological Informat- ion, XML Documents, Images and Social Network etc. The basic operation of Graph is graph query processing. Classic graph query ques- tion is： given a graph database D and a query q, retrieve all graph in D which contain q as sub-graph（s）. In this paper, for given que- ry q , an effective index strategy is developed, extracting discriminate tree as features tree, encoding features tree, converting structure compared to encode sequence matching, and make use of features tree to create index, simultaneously, two pruning strategy are pro- posed, Filter out these graphs in D which do not match q aecurately. Experimental results verify the usefulness and effectiveness of proposed subgraph query processing algorithm.