基于DFS编码的图形数据库Top-K查询技术研究

摘要

图形是一种描述性很强的数据结构。通过加以标记的顶点和边，图形既可以深入描述一组实体间的关系，也可以直观地描述这些关系间的属性。在复杂结构数据建模方面，如化合物分子结构，蛋白质基因结构，电路结构，Web和XML文档等，图形起着很重要的作用，图形数据库也由此得到广泛的关注和应用。在与图形相关的应用中，存在一个共同且关键的问题，即如何有效地处理图形查询和检索问题。通常，应用是否成功直接依赖于查询处理系统的有效性。
　　 本文主要讨论图形数据库的Top-K查询问题，即给定一个查询图，返回数据库中与其最相似的K个图形。将查询图与数据库中的图逐个地进行两两比较是非常耗时的。一般地图形数据库的查询主要分为查询过滤和查询验证两个阶段。在过滤阶段中，数据库中不符合条件的图应尽可能多地被过滤，并生成一个候选图形集合。在查询验证阶段，进一步筛除掉不满足条件的图形，获得最终结果。在过滤阶段，关注如何对图形建立索引以减小候选图形集合。在验证阶段，一般使用子图同构技术进行验证。
　　 针对图形数据库查询处理和优化需求，重点分析和研究了图形数据库的索引技术和图形同构技术，在上述的两个技术中均使用DFS编码对图进行序列化。在此基础上，进一步研究了图形数据库的Top-K查询。
　　 在图形数据库的索引技术方面，提出基于频繁语义结构的图形数据库的索引方法，称为GSIndex。GSIndex使用GString技术来表示图形，把图形表示成由语义信息的裂片组成的串，然后找出频繁的具语义信息的裂片，用DFS编码对这些裂片进行序列化，在此基础上对这些裂片构造索引树。由这些有语义的裂片构造的索引更加贴近实际的应用。
　　 在图形同构方面，通过深入分析经典图形同构的算法，根据最小DFS编码的性质，即两个图同构当且仅当它们的最小DFS编码相同，提出了基于DFS编码的子图同构算法。
　　 在Top-K查询方面，根据图形相似性的度量标准，提出基于GSIndex技术的Top-K查询方法，并论述了两种新的查询方式：析取查询和合取查询。这两种查询方式可以根据用户的需要，按照部分特定的基本子图及它们间的逻辑组合关系进行查询。
　　 实验结果表明，以上技术和方法可有效提高过滤率和验证的准确性，提高查询性能。

目录

文摘

英文文摘

第1章 绪论

1.1. 研究背景

1.2. 图形数据库Top-K查询的主要问题和国内外研究现状

1.2.1. 研究的主要问题

1.2.2. 研究现状

1.3. 论文研究内容和结构

第2章 图形数据库查询的索引构造方法

2.1. 引言

2.2. 图形数据库的基本概念

2.3. 典型的图形数据库的索引方法

2.3.1. 基于路径的索引-GraphGrep

2.3.2. 基于频繁结构的索引-Ginldex

2.3.3. 图到序列的转化-Gstrin

2.4. 基于频繁语义结构的图形数据库的索引方法

2.4.1. 频繁结构

2.4.2. Gstring技术

2.4.3. 图的序列化

2.4.4. 索引构造

2.5. 实验

第3章 子图查询

3.1. 引言

3.2. 基于矩阵变换的同构算法

3.2.1. 图的矩阵变换

3.2.2. 图同构矩阵变换算法

3.2.3 图同构实例应用分析

3.3. 图同构问题粒子群算法

3.3.1. 粒子群算法原理

3.3.2. 离散粒子群算法求解图同构

3.4. 基于DFS编码的图形同构算法

3.4.1. 最小DFS编码的求解

3.4.2. 子图同构算法

3.5. 实验

第4章 图形数据库Top-K查询

4.1. 引言

4.2. 图形相似的度量标准

4.2.1. 编辑距离(edit距离)

4.2.2. 最大公共子图

4.2.3. 基于拓扑子图与编辑距离的距离测量方法

4.3. 基于频繁语义结构的图形数据库的索引方法上的Top-K查询

4.4. Top-K查询扩展

4.4.1. 合取查询

4.4.2. 析取查询

4.5. 实验

第5章 总结与展望

5.1. 论文研究工作总结

5.2. 有待进一步研究的问题

致谢

参考文献

作者在攻读硕士学位期间发表的学术论文