图数据查询技术的研究

《图数据查询技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、博士学位论文图数据查询技术的研究ResearchofQueryTechnologiesonGraphData李先通哈尔滨工业大学2009年6月国内图书分类号：TP311.13学校代码：10213 国际图书分类号：681.5密级：公开工学博士学位论文图数据查询技术的研究博士研究生：李先通导师：李建中教授申请学位：工学博士学科：计算机软件与理论所在单位：计算机科学与技术学院答辩日期：2009年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP311.13 U.D.C.:681.5Dissertationforth

2、eDoctoralDegreeResearchofQueryTechnologiesonGraphDataCandidate:XiantongLiSupervisor:ProfessorJianzhongLiAcademicDegreeAppliedfor:DoctorofEngineeringSpecialty:ComputerSoftwareandTheoryAffiliation:SchoolofComputerScienceandTechnologyDateofDefence:June,2009Degree-Confe

3、rring-Institution:HarbinInstituteofTechnology摘要摘要图是一种通用的数据结构，能描述复杂的结构化或半结构化数据，如：XML、WWW、社会关系网络、化合物集合、蛋白质与基因网络等等。随着图在 各领域内的成功应用，图数据开始迅速累积。然而，数据量的增加，不但没有带 来信息获取的便利，反而由于图数据的复杂本质，使得学习与研究工作更难展 开。图查询是图数据集上的一个典型应用，用于从海量图数据中获取用户需要 的知识。与传统查询技术相比，图查询具有自己的特点与难点，如：数据结构复杂，操控困难；子

4、图同构已被证明是NP完全问题，是图查询领域中不可避免的 基本操作之一；图数据种类繁杂，等等。正是这些难点，导致图查询技术的研究 充满了机遇与挑战。本文通过对图数据查询技术的研究，归纳总结了现有研究成果的思想和优 缺点，重点研究了频繁子图查询、超图查询、包含查询、相交子图查询等技术专 题，主要的研究成果与创新如下：第一、现有效率较高的频繁子图模式查询算法，在生成频繁子图的过程中， 对边的扩展通常采用深度优先的方法。而且，对频繁子图的每次扩展，均需要通 过子图同构计算验证其正确性。然而，深度优先的扩展方式虽然能有效避免查 询算法重

5、复生成中间结果，却带来了更高的时间复杂性。本文提出了一种高效 的频繁子图查询算法，通过先生成频繁子树，进而通过这些频繁子树进一步生 成频繁子图。在生成频繁子树的过程中，采用深度优先的遍历方式避免中间结 果的重复计算，并利用子树同构可在多项式时间内完成的特点提高该部分算法 的效率。另一方面，在由子树向子图扩展的过程中，通过广度优先的方式进行扩 展，不但能有效避免中间结果的重复生成，而且进一步提高了算法的效率。理论分析与实验结果显示，采用这种查询方法，使查询效率提高了O(√n·logn)倍，并在提高效率的同时，得到正确的结果集。第

6、二、超图查询算法采用过滤与验证模式，即：通过对图集的过滤，得到更小、更精确的候选集，从而降低查询过程中子图同构次数，进而提高算法的效率。超图查询的过滤规则为包含逻辑，即如果甲图包含乙图，则甲图必然包含乙图的所有子图。查询算法的索引通常建立于图集中的频繁模式，包括频繁子图、频繁子树或频繁路径等。然而，在给定查询图之后，无论何种索引，均需要得到查询图包含的索引模式，并通过索引模式支持集的交集得到候选集。在–I–哈尔滨工业大学工学博士学位论文得到查询图包含的索引模式过程中，需要进行查询图子图枚举，并与索引模式之间进行子图同构，得到查

7、询图包含的索引模式。本文提出查询算法VFM，通过图集中关键节点与频繁模式之间的映射，将得到被查询图包含的索引模式的过程由指数形式降低为多项式形式，从而显著提高了算法效率。实验结果表明，采用该算法进行查询，其效率远高于当前已经提出的算法。第三、图查询问题包含的另一类查询问题，称为包含查询。包含查询与超图查询的本质区别在于，它采用的过滤手段为排除逻辑，即：给定查询图，如果图集中的图数据包含的某个模式不是查询图的子图，则该图也必定不是查询图的超图。利用排除逻辑建立的索引，在查询之初，同样要通过枚举或与索引模式之间逐个的子图同构计算得

8、到不被查询图包含的索引模式，这是需要尽力避免的计算开销。本文针对图包含查询中存在的问题，提出利用频繁子图查询过程中形成的深度优先树组织索引，能增量地进行查询图与索引模式之间的子图同构计算。而且，在索引模式的选择中，提出采用频繁模式集中一类特殊的子集——频繁闭模式来建立索引，这