基于特征索引的图查询研究

论文摘要

随着现代化信息技术的迅猛发展,人们对复杂事物建模的需求也越来越大。图作为一种能模拟复杂事物之间联系的数据结构在数据挖掘中显得越来越重要,表现在它能够表达更加丰富的语义和结构。目前,图已应用于很多领域,如化学领域、社会网络领域、模式匹配领域、XML领域等。图查询作为图数据集上的一个经典应用,从海量的图数据中获取用户想要的数据。目前,图查询策略主要是采用一种图数据库建立索引-过滤-精华提纯的过程,所以本文把对图索引的构造和过滤的研究作为研究重点。首先,本文介绍了图的相关基本概念、图查询算法的类型和图索引机制的算法分类,分别对基于结构的图索引算法和基于特征的图索引算法做了进一步地分析,归纳得出这些算法的优点和缺点,为图索引的建立奠定理论基础。其次,本文根据频繁图查询中遇到的问题,深刻研究了图查询的整个过程和图查询代价,提出了一种新的图索引算法。算法首先生成频繁子图的特征图,然后再对特征图进行分解,并验证特征图是否加入到无回路图中形成结点,最终分解得到的标准编码,再将这标准编码放入对应的哈希表里,并得出了最终的图索引结构。再次,本文提出了基于图特征索引的过滤算法,把图对边的放松查询转化为最大允许的损失特征数,利用特征聚合分层重新建立了图特征之间的关系,对特征集进行了分类排序,使得图查询过滤更加精确和高效。最后,本文通过实验对算法进行了验证,并将结果与现有算法做了对比,详细地分析了实验结果,进而验证了此算法的高效性和准确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 研究意义
• 1.4 研究内容
• 1.5 本文结构
• 第2章 基础知识概述
• 2.1 引言
• 2.2 图基本定义
• 2.3 图查询的类型
• 2.3.1 匹配性查询
• 2.3.2 相似性查询
• 2.3.3 相关性查询
• 2.4 基于结构的图索引机制
• 2.5 基于特征的图索引机制
• 2.5.1 GraphGrep 算法
• 2.5.2 GIndex 算法
• 2.6 本章小结
• 第3章 基于特征的图索引算法
• 3.1 引言
• 3.2 图查询的过程分析
• 3.3 图查询代价分析
• 3.4 索引算法GDFIndex 思想
• 3.5 图序列化-图标准编码
• 3.6 生成特征图
• 3.7 对特征图的分解
• 3.8 HASH 表
• 3.9 GDFIndex 算法描述
• 3.10 本章小结
• 第4章 基于特征索引的图相似查询算法
• 4.1 引言
• 4.2 SFGF 算法思想
• 4.3 SFGF 算法
• 4.3.1 基本定义
• 4.3.2 改进的SFGF 算法
• 4.4 SFGF 算法描述
• 4.5 相似查询算法描述
• 4.6 本章小结
• 第5章 实验及结果分析
• 5.1 引言
• 5.2 实验设备和开发环境
• 5.3 GDFIndex 算法的实验分析
• 5.3.1 真实数据集
• 5.3.2 人工模拟数据集
• 5.4 SFGF 算法的实验分析
• 5.4.1 实验数据集
• 5.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢
• 作者简介