图数据查询技术的研究

论文摘要

图是一种通用的数据结构,能描述复杂的结构化或半结构化数据,如:XML、WWW、社会关系网络、化合物集合、蛋白质与基因网络等等。随着图在各领域内的成功应用,图数据开始迅速累积。然而,数据量的增加,不但没有带来信息获取的便利,反而由于图数据的复杂本质,使得学习与研究工作更难展开。图查询是图数据集上的一个典型应用,用于从海量图数据中获取用户需要的知识。与传统查询技术相比,图查询具有自己的特点与难点,如:数据结构复杂,操控困难;子图同构已被证明是NP完全问题,是图查询领域中不可避免的基本操作之一;图数据种类繁杂,等等。正是这些难点,导致图查询技术的研究充满了机遇与挑战。本文通过对图数据查询技术的研究,归纳总结了现有研究成果的思想和优缺点,重点研究了频繁子图查询、超图查询、包含查询、相交子图查询等技术专题,主要的研究成果与创新如下:第一、现有效率较高的频繁子图模式查询算法,在生成频繁子图的过程中,对边的扩展通常采用深度优先的方法。而且,对频繁子图的每次扩展,均需要通过子图同构计算验证其正确性。然而,深度优先的扩展方式虽然能有效避免查询算法重复生成中间结果,却带来了更高的时间复杂性。本文提出了一种高效的频繁子图查询算法,通过先生成频繁子树,进而通过这些频繁子树进一步生成频繁子图。在生成频繁子树的过程中,采用深度优先的遍历方式避免中间结果的重复计算,并利用子树同构可在多项式时间内完成的特点提高该部分算法的效率。另一方面,在由子树向子图扩展的过程中,通过广度优先的方式进行扩展,不但能有效避免中间结果的重复生成,而且进一步提高了算法的效率。理论分析与实验结果显示,采用这种查询方法,使查询效率提高了O(√n·logn)倍,并在提高效率的同时,得到正确的结果集。第二、超图查询算法采用过滤与验证模式,即:通过对图集的过滤,得到更小、更精确的候选集,从而降低查询过程中子图同构次数,进而提高算法的效率。超图查询的过滤规则为包含逻辑,即如果甲图包含乙图,则甲图必然包含乙图的所有子图。查询算法的索引通常建立于图集中的频繁模式,包括频繁子图、频繁子树或频繁路径等。然而,在给定查询图之后,无论何种索引,均需要得到查询图包含的索引模式,并通过索引模式支持集的交集得到候选集。在得到查询图包含的索引模式过程中,需要进行查询图子图枚举,并与索引模式之间进行子图同构,得到查询图包含的索引模式。本文提出查询算法VFM,通过图集中关键节点与频繁模式之间的映射,将得到被查询图包含的索引模式的过程由指数形式降低为多项式形式,从而显著提高了算法效率。实验结果表明,采用该算法进行查询,其效率远高于当前已经提出的算法。第三、图查询问题包含的另一类查询问题,称为包含查询。包含查询与超图查询的本质区别在于,它采用的过滤手段为排除逻辑,即:给定查询图,如果图集中的图数据包含的某个模式不是查询图的子图,则该图也必定不是查询图的超图。利用排除逻辑建立的索引,在查询之初,同样要通过枚举或与索引模式之间逐个的子图同构计算得到不被查询图包含的索引模式,这是需要尽力避免的计算开销。本文针对图包含查询中存在的问题,提出利用频繁子图查询过程中形成的深度优先树组织索引,能增量地进行查询图与索引模式之间的子图同构计算。而且,在索引模式的选择中,提出采用频繁模式集中一类特殊的子集——频繁闭模式来建立索引,这种方式不但能极大化地减小候选集的尺寸,同时也避免了过多子图同构计算所带来的负面影响,从而提高了算法的效率。第四、图集的查询问题,并不能完全通过频繁子图查询、超图查询与包含查询解决。相交子图查询问题,能在某些条件下转化为超图查询或包含查询。然而,超图查询或包含查询解决相交子图查询问题时,需要重复进行多次查询,方可得到查询结果,效率低下。针对相交子图查询问题,目前尚无研究结果发表。本文率先提出的相交子图查询算法,通过对数据库图解构,形成基于节点诱导连通子图的有向无环图,并通过边列表对有向无环图的节点信息进行补充,不但能高效完成相交子图的查询工作,而且将索引的规模控制在了适当的范围之内。相交子图查询能解决图集中一类查询问题,因而,本文作为首篇提出该查询算法的文献,意义深远。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 图数据查询应用背景
• 1.2 图查询研究现状
• 1.3 图数据查询技术综述
• 1.3.1 频繁子图查询
• 1.3.2 相关图查询
• 1.3.3 有向图节点可达性查询
• 1.4 图查询技术相关问题研究
• 1.4.1 图的简化描述
• 1.4.2 图分类
• 1.4.3 动态图研究进展
• 1.4.4 图核函数
• 1.5 本文主要研究工作
• 1.5.1 本文的研究背景
• 1.5.2 本文主要研究内容
• 1.5.3 本文主要的研究成果
• 1.5.4 本文的章节安排
• 第2章 频繁子图查询算法
• 2.1 引言
• 2.2 与频繁图模式查询相关的基本概念
• 2.3 频繁图模式查询算法
• 2.3.1 标号图的标准化编码
• 2.3.2 频繁树模式查询算法（ FTGen）
• 2.3.3 频繁图模式查询算法（GraphGen）
• 2.3.4 算法的优化
• 2.4 实验结果与分析
• 2.4.1 模拟数据集上的实验结果与分析
• 2.4.2 真实数据集上的实验结果与分析
• 2.5 本章小结
• 第3章 超图查询处理
• 3.1 引言
• 3.2 问题定义
• 3.3 超图查询处理算法VFM
• 3.3.1 VFM-Index
• 3.3.2 索引构建算法
• 3.3.3 查询算法VFM-Query
• 3.4 算法效率分析
• 3.5 实验结果
• 3.5.1 真实数据集
• 3.5.2 模拟数据集
• 3.6 本章小结
• 第4章 包含查询处理
• 4.1 引言
• 4.1.1 相关工作
• 4.1.2 本章的贡献
• 4.2 问题定义
• 4.2.1 图的标准代码
• 4.2.2 图包含查询
• 4.3 图包含查询处理
• 4.3.1 频繁子图与频繁闭图
• 4.3.2 CFG-Index
• 4.3.3 查询处理算法
• 4.4 性能分析
• 4.4.1 索引模式过滤
• 4.4.2 折半查找
• 4.5 实验结果
• 4.5.1 真实数据
• 4.5.2 模拟数据
• 4.6 本章小结
• 第5章 相交子图查询处理
• 5.1 引言
• 5.2 相关工作
• 5.3 相关定义
• 5.3.1 相交子图查询
• 5.3.2 图标准编码
• 5.4 基于节点的连通子图索引
• 5.4.1 图的分解
• 5.4.2 Hash 表
• 5.4.3 索引构建算法
• 5.5 查询算法
• 5.6 实验结果
• 5.6.1 真实数据集
• 5.6.2 模拟数据集
• 5.7 本章小结
• 结论
• 参考文献
• 附录A 符号与缩略语表
• 攻读博士学位期间发表的学术论文及其它成果
• 致谢
• 个人简历