基于频繁结构的大规模动态图子图查询方法研究

论文摘要

随着科技的不断进步和发展,图作为一种重要的数据结构已广泛应用于各种新兴领域,如社交网、蛋白质交互网、生物信息网、智能交通网等。近年来,互联网用户数量的飞速增长和网络技术的深度发展,导致图数据规模日益庞大且动态变化。如何对大规模动态图进行有效的管理成为当前图数据领域研究的热点问题。子图查询作为重要的图搜索技术,因为其可以更具针对性地为用户返回查询结果而被广泛研究。传统算法处理大规模图子图查询效率低下,现有子图查询方法多通过建立索引或进行图压缩来加快查询。频繁结构在数据图中频繁稳定存在,并隐藏大量有用信息,很多方法对其建立索引以加速查询。但其多受查询图类型限制,难以满足任意查询需求并适应于任意大图数据查询。此外,已有研究多忽略大图数据的快速更新,难以处理动态图查询。为此,本文利用索引查询优势,提出了一种基于频繁结构的大规模动态图子图查询方法（subgraph query based on frequent structure in large-scale dynamic graph,FS-DSQ）。本文的主要研究工作如下:（1）充分分析频繁结构特征,提出旋转对称频繁结构,线下挖掘数据图中的该结构及对应子图,并建立旋转对称频繁结构索引（RSFS索引）以方便查询。提出索引的增量式动态维护策略,充分考虑频繁I/O及网路通信开销等因素,利用定时更新取代实时更新,根据变化类型不同,提出点、边增加和点、边删除两种动态维护策略,只对变化的索引项进行更新,避免全局更新带来的巨大开销。（2）提出大规模动态图子图查询方法,包括查询图分解、基于RSFS索引的动态查询。首先,提出基于最大分解原则的查询图拆解算法,将查询图逐步拆解为RSFS索引中其最大子集结构的集合。然后,进行子图优化查询与连接。利用RSFS索引对各拆解结构进行优化查询,利用前置结构查询序列L及公共点等信息形成查询约束,约束后置结构查询,快速过滤掉不满足约束的子图结果,仅保留有效的可连接子图结果集。利用旋转对称结构特征优势,对中间结果进行快速连接,形成查询结果。最后,利用收集的图变化操作,动态修正查询结果,以获得最终查询结果。（3）基于真实数据集和模拟数据集进行实验验证,从索引创建时间、存储开销、子图查询时间、索引更新时间四个方面与多种算法进行对比,在空间和时间上证明了本文算法的有效性。

论文目录

摘要

abstract

第1章引言

1.1 研究背景与意义

1.2 问题提出

1.3 研究内容

1.4 本文组织结构

第2章相关工作

2.1 图

2.2 现有子图查询方法

2.2.1 基于压缩的子图查询

2.2.2 基于索引的子图查询

2.2.3 动态图查询相关算法

2.3 本章小结

第3章旋转对称频繁结构索引

3.1 问题描述

3.2 旋转对称频繁结构索引创建

3.2.1 旋转对称频繁结构挖掘

3.2.2 RSFS索引创建

3.2.3 实例

3.3 RSFS索引动态维护

3.3.1 点、边增加动态维护

3.3.2 点、边删除动态维护

3.4 本章小结

第4章大规模动态图子图查询方法

4.1 问题描述

4.2 查询图分解

4.2.1 基于最大分解原则的查询图拆解算法

4.2.2 实例

4.3 基于RSFS索引的动态查询

4.3.1 子图优化查询

4.3.2 中间结果连接

4.3.3 动态修正

4.4 本章小结

第5章实验与分析

5.1 实验设置

5.1.1 实验环境及方案

5.1.2 实验数据集

5.2 实验结果与分析

5.2.1 索引创建时间

5.2.2 存储开销

5.2.3 子图查询时间

5.2.4 索引更新时间

5.3 本章小结

第6章结论与展望

6.1 结论

6.2 展望

致谢

参考文献

攻读学位期间发表的学术论文及参加科研情况

文章来源

类型: 硕士论文

作者: 王广香

导师: 宋宝燕

关键词: 大规模动态图,子图查询,旋转对称频繁结构,查询图分解,动态查询

来源: 辽宁大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 辽宁大学

分类号: O157.5

总页数: 64

文件大小: 3144K

下载量: 32

基于频繁结构的大规模动态图子图查询方法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢