图索引技术新方法

论文摘要

随着结构化数据在互联网应用中的大量出现,对复杂数据进行图建模在近年来越来越流行。图索引问题在图数据库应用中至关重要。本文主要研究了图数据库上的图索引问题。本文提出了MSTA索引方法及MSTA索引方法上的子图查询算法、超图查询算法、相似性查询算法和相关性查询算法。MSTA索引方法利用最小生成树作为数据特征,将所有的最小生成树依据边序列的包含关系和最大公共子图距离度量组织成MST树索引结构,高效的支持各种查询算法。传统索引方法的索引大小和索引建立时间是MSTA索引方法的数十倍,甚至上百倍。MSTA索引方法上的查询算法都是近似的,返回的结果是最好的部分结果。我们还分析了MSTA索引方法的原理和正确性。实验结果辅证了该索引方法的高效索引性能及查询性能。本文提出了RQ索引方法及RQ索引方法上的相关性查询算法。我们分析了相关性查询算法的代价组成,从而得出代价影响的两个结论;分析了已有索引方法在支持相关性查询上的不足。RQ索引方法,利用四种不同维度选择策略得到高维空间矩阵作为数据特征,将所有的高维空间矩阵组织到R树索引结构中。实验结果表明,RQ索引方法具有优秀的索引性能,并具有很好的可扩展性。RQ索引方法可以高效的支持相关性查询。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景及研究的目的和意义
• 1.2 国内外的研究现状
• 1.2.1 以特征为中心的索引方法的研究现状
• 1.2.2 以结构为中心的索引方法的研究现状
• 1.3 本文的研究内容
• 1.4 本文的结构
• 第2章 查询定义与底层算法
• 2.1 查询定义
• 2.1.1 图的匹配性查询
• 2.1.2 图的相似性查询
• 2.1.3 图的相关性查询
• 2.2 底层算法
• 2.2.1 子图同构测试算法
• 2.2.2 频繁子图挖掘算法
• 2.2.3 R树维护算法
• 2.3 本章小结
• 第3章 MSTA索引方法及查询算法
• 3.1 MSTA的研究动机
• 3.2 MSTA的索引方法
• 3.2.1 最小生成树产生算法
• 3.2.2 最小生成树子树测试算法
• 3.2.3 最大公共子图的图距离度量
• 3.2.4 MST树索引建立算法
• 3.3 MSTA的索引原理
• 3.3.1 理论证明
• 3.3.2 理论分析
• 3.4 MSTA的查询算法
• 3.4.1 子图查询算法
• 3.4.2 超图查询算法
• 3.4.3 相似性查询算法
• 3.4.4 相关性查询算法
• 3.5 实验结果分析
• 3.5.1 MST树索引性能
• 3.5.2 子图查询的性能
• 3.5.3 超图查询的性能
• 3.5.4 相似性查询的性能
• 3.5.5 相关性查询的性能
• 3.6 本章小结
• 第4章 RQ索引方法及查询算法
• 4.1 RQ的研究动机
• 4.2 相关性查询分析
• 4.2.1 相关性查询的算法思想及代价分析
• 4.2.2 已有索引方法对相关性查询的支持
• 4.3 RQ的索引方法及查询算法
• 4.3.1 索引建立算法
• 4.3.2 相关性查询算法
• 4.3.3 维度特征选择策略
• 4.4 实验结果分析
• 4.4.1 边特征RQ索引的索引性能
• 4.4.2 边特征RQ索引的查询性能
• 4.4.3 频繁子图特征RQ索引的索引性能
• 4.4.4 频繁子图特征RQ索引的查询性能
• 4.5 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢