论文部分内容阅读
图是一种通用的数据结构,相比路径和树结构来说,图能表达更多复杂的结构信息,如:分子结构、社交网络关系、图像。近年来,随着图数据在各个应用领域内被广泛使用,其数据量成指数级迅速积累,导致对这些海量数据的管理成为一项重要的研究工作。图数据管理中重要的分支之一是子图查询技术研究。图查询技术具有自己的特点与难点:1、数据结构相对其他较复杂,操纵困难。2、子图同构问题在精确子图查询过程中是不可避免的,而且已被证明是NP难问题。3、图数据种类繁杂。为了解决这一系列的问题,使得图查询技术的研究充满了挑战与机遇。本文针对图数据库中的精确子图查询技术,主要完成了以下工作:(1)根据现有频繁子图挖掘算法,选取高效的频繁子图挖掘算法作为本论文的离线挖掘算法。通过对AGM、FSG、g Span算法的对比,得出基于深度挖掘的g Span算法的通用性与高效性,相比基于宽度优先挖掘的算法来说:1、使用DFS码对图进行编码,避免了匹配过程中的子图同构问题。2、避免了Apriori逐层扩展产生的大量中间结果带来的计算开销。(2)结合频繁模式特征挖掘算法,提出一种新的基于频繁子图中邻接边哈希索引构建方法AG-Index:利用过滤-验证模型,对频繁图部分构建索引存入缓存内,非频繁部分放在磁盘,得到候选项后用现有效率较高的子图同构算法进行验证。实验证明,AG-Index比经典高效的g Index和FG-Index算法过滤能力更强,内存占有率更小,并在AG-Index的基础上对其进行了更进一步的优化,实验证明,其过滤能力在AG-Index上有所提升,其他方面有待探究。(3)子图同构算法设计,结合现有常用Ullmann、VF2子图同构算法:1、在Ullmann算法基础上利用邻接边结构等信息对其进行剪枝,实验证明,剪枝后的Ullmann查询效率比剪枝前提高了一个数量级。2、在VF2算法上调整顶点的考察匹配顺序,实验证明与按标号大小顺序遍历节点相比,按节点度数大小顺序匹配在图大小为8时的效率更高,更容易快速剪枝不是子图同构的情况。