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

摘要：

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

关键词：子图查询、特征选取、索引结构、剪枝

所属期刊栏目：34

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金项目60673136;河北省自然科学基金项目F2012203143;河北省教育厅2009年自然科学研究计划项目2009101

在线出版日期：2013-05-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：370-374