基于图编码的索引和同构查询处理技术

论文摘要

图是一种基本的数据结构,是计算机领域重要的研究对象。随着计算机网络技术的不断发展和对于图数据的存储管理需求与日俱增,围绕图数据的研究在近年来引起高度的重视。其中,图数据索引结构的构建和图同构的查询处理是进行其他关于图数据操作的基础工作,也是最有挑战性的关键技术之一。本文的研究工作主要集中在对图数据索引的建立、图同构的判定、及图编码等相关技术的深入研究,同时,在原有的研究基础上,提出了一种新的、基于编码的图索引结构,和同构查询处理方法。该技术的基本思想在于：设计一种易于编码的图存储结构,以满足图与编码的一一映射关系,并且图编码的集合具有一个偏序关系,使得任意两个图的编码(将图编码转换成对应的向量)之间都存在明确的大小关系,以便于改进现有的索引结构来提高查询的效率。本文提出的基于图编码的索引和图同构查询处理技术的贡献点,有如下几方面：第一,提出了“最大邻接矩阵”的概念。它是一种图的存储结构,能够满足编码与图的一一映射关系,从而很好的解决多年来难以解决的一个图对应很多个存储形式的一对多关系,同时它本身又是一种图的邻接矩阵,能够很好的兼容现存的其他图存储方式；第二,设计了一种的图编码方式。这种与图一一对应的图编码方式能够很好的应用于图同构的判定,任何两个图的编码之间都是有大小关系的,只有同构的图才具有相同的编码,这样就可以通过比较编码字符的方式来完成同构的判定,并且实验证明这种方法在响应时间上比传统的图同构判定方式有明显的优势。第三,建立索引结构来支持图同构查询。以往的图同构查询多是采用遍历和剪枝的方式,而用利用索引来支持同构查询,可以有效的避免遍历,减少比对次数,从而提高查询效率。最后,通过实验证明,本文提出的基于编码的图索引和同构查询处理技术与传统的图同构判定和查询方式相比,查询效率有所提高,特别是在解决较大规模的图和边密度较大图的情况中,它的判定效率和查询效率都有十分明显的提高,表现出了很好的可用性和高效性。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 图的发展历程
• 1.2 图数据库的发展现状
• 1.3 论文组织结构
• 第2章 相关概念与研究进展
• 2.1 图的基本定义及术语
• 2.2 图的存储方式
• 2.3 图同构
• 2.3.1 图同构的复杂性分析
• 2.3.2 图同构的判定方法
• 2.3.3 判定图同构的经典算法
• 2.4 图编码技术
• 2.4.1 树的编码
• 2.4.2 三角图的编码
• 2.4.3 子图同构中的图编码技术
• 2.5 本章小结
• 第3章 基于编码的图查询处理
• 3.1 图对象设置和标准化处理
• 3.2 索引结构设计
• 3.3 索引的建立与维护
• 3.4 图数据的查询
• 3.5 本章小结
• 第4章 图数据的标准化存储
• 4.1 结点序列化
• 4.2 最大化邻接矩阵
• 4.2.1 最大邻接矩阵的相关概念
• 4.2.2 最大邻接矩阵与图的关系分析
• 4.2.3 最大邻接矩阵的性质
• 4.3 无向无标签简单图的最大化算法
• 4.3.1 无向无标签简单图及其属性
• 4.3.2 无向无标签简单图的邻接矩阵
• 4.3.3 MaxMatrix算法
• 4.4 本章小结
• 第5章 基于编码的图数据索引
• 5.1 基于编码的图同构判定方法
• 5.1.1 图的最大编码
• 5.1.2 最大编码的优化
• 5.1.3 图同构的判定
• 5.2 索引的建立
• 5.3 索引的维护
• 5.3.1 图数据空间上的同构查询
• 5.3.2 插入图数据的操作
• 5.3.3 删除图数据的操作
• 5.4 本章小结
• 第6章 实验与性能分析
• 6.1 实验环境介绍
• 6.2 数据集介绍
• 6.3 实验设计与性能测试
• 6.3.1 两图的同构关系的判定
• 6.3.2 数据集上的图同构查询处理
• 6.4 实验数据分析
• 6.5 本章小结
• 第7章 总结与展望
• 7.1 论文总结
• 7.2 技术展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文和参加的项目