图数据库中的子图查询算法研究

论文摘要

图是计算机科学中的重要数据结构。随着信息技术地不断发展，出现了越来越多的以图作为逻辑表达的数据，例如化学分子结构式，生物网络，社会网络以及图像中的实体关系等等。另一方面，这些图数据本身的数据量也在不断增大，例如每天就有4,000个新的化学结构被加入到SCF Finder数据库；现在的社会网络图中的结点数目超过了1亿5千万。如何有效地管理和挖掘海量的图数据是图数据库研究的核心问题。具体包括：1)如何建立有效的存储机制和索引策略；2)如何有效地回答图数据库中的查询；3)如何从海量的图数据库中挖掘出有用的信息。子图查询是图数据管理中的基本操作。具体地说，给定一个查询图Q，在图数据库中找到所有包含查询图Q的数据图。由于子图同构是典型的NP完全问题，目前的子图查询算法均采用“过滤-精化”的算法来找到结果集。在过滤阶段，根据某种子图同构的必要条件过滤掉不可能包含查询图Q的数据图；然后在精化阶段利用子图同构算法在剩下的数据图中找到结果集。目前的大部分的过滤策略都是基于“特征子结构”（简称“特征”）的方法。这种方法没有考虑到特征之间的拓扑关系。根据特征和特征之间的拓扑关系，设计一种新的过滤策略将加快子图查询的响应时间。另外目前的子图查询算法没有考虑数据库频繁动态更新的情况。当数据库出现增删改时，不得不重新建立索引。为了适应动态的图数据库，根据图谱理论，将图的拓扑信息映射到数据空间中；并根据映射的数值空间，建立相应的索引结构。这种方法不但加快了过滤的时间，而且可以动态的维护索引结构。随着社会网络等复杂网络的出现，给定查询图Q，如何在一张大图中找到Q的匹配位置是非常有意义的课题，例如可以帮助我们找到社会网络中的特定的朋友圈，以及生物网络中的功能团。大图上的匹配的定义本身并一定是基于子图同构。因为网络上考虑的更多的是两点之间的连接性关系。根据连接性关系，找到查询图Q的所有匹配位置。因为通常复杂网络中的节点数目是海量的，为了减少搜索空间，将图结构中映射到向量空间。通过在向量空间的操作，找到所有的候选匹配位置；然后在原来的图结构中确定最终的匹配结果集。图数据挖掘可以帮助我们从海量的图数据中找到有用的知识，其中频繁结构模式挖掘和结构相关性挖掘是两个重要的课题。目前的结构模式挖掘算法大部分采用“生成-检测”的算法框架。这种方法的缺点是“检测”阶段耗费大量时间。根据图数据的特例“树数据”的特点，采用模式增长的方式设计频繁结构模式挖掘算法，从而避免了检测阶段。给定一个查询图Q，希望从图数据库中找到与Q具有高度相关性的子结构。这个问题的难点在于海量的搜索空间。为了加快算法响应时间，根据模式增长的策略，设计一种有效的过滤策略。用图结构来表示关系型数据库中的记录之间的“控制”关系，从而将传统的Top-K查询问题转换为图结构中的遍历问题。与现有的经典Top-K查询算法相比，这种方法的优点是其搜索空间较小。

论文目录

• 摘要
• Abstract
• 目录
• 1 绪论
• 1.1 研究背景
• 1.2 研究课题和主要贡献
• 1.3 国内外研究现状
• 1.4 本文组织结构
• 2 频繁子树模式挖掘算法
• 2.1 基于模式增长的频繁子树挖掘算法PrefixTreeESpan
• 2.2 PrefixTreeESpan性能评测
• 2.3 带子树约束的频繁子树挖掘算法SCFS
• 2.4 SCFS性能评估
• 2.5 本章小节
• 3 基于特征模式的图数据库索引机制
• 3.1 基于“特征+距离”的索引机制
• 3.2 实验比较
• 3.3 本章小结
• 4 基于图谱编码的子图查询算法
• 4.1 背景知识
• 4.2 图编码
• 4.3 子图查询
• 4.4 实验研究
• 4.5 本章小结
• 5 Top-K相关子图查询算法
• 5.1 背景知识
• 5.2 PG-Search算法
• 5.3 实验研究
• 5.4 本章小结
• 6 基于距离连接的子图模式匹配算法
• 6.1 图的距离编码
• 6.2 问题定义和匹配算法框架
• 6.3 邻居区域过滤策略
• 6.4 边查询处理
• 6.5 子图模式匹配查询
• 6.6 实验分析
• 6.7 本章小结
• 7 一种有效的基于图的索引策略
• 7.1 背景知识
• 7.2 基于DG索引的Traveler算法
• 7.3 高级Traveler算法
• 7.4 DG图索引的动态维护算法
• 7.5 实验研究
• 7.6 本章小结
• 8 总结与展望
• 8.1 工作总结
• 8.2 研究展望
• 致谢
• 参考文献
• 附录1 攻读学位期间发表的学术论文
• 附录2 攻读学位期间完成和参与的项目