一种面向无向加权图的子图查询方法

论文摘要

随着图结构的大规模应用,图数据库上的查询已经成为图挖掘的研究热点。针对无向加权图,本文提出一种基于最短权值路径和拉普拉斯图谱的子图查询方法PSQuery。首先,PSQuery方法选取可表示数据图的高效特征属性;接着,对提取的特征属性按照哈希映射进行编码,将特征编码组合生成节点编码和图编码,并且基于图编码构建索引树;最后,通过实现过滤-验证框架得到结果集:按照提取特征的嵌套性质进行过滤生成候选集,再根据VF2算法进行验证得到最终的超图集合。实验结果表明,提出的方法加速了无向加权图数据库上的子图查询过程,提高了查询效率。

论文目录

• 1 相关工作
• 2 PSQuery编码和索引方法
•   2.1 图谱及路径的相关性质
•   2.2 数据图的编码
•   2.3 索引的建立
• 3 PSQuery的查询处理
•   3.1 过滤过程
•   3.2 验证过程
• 4 实验结果和分析
•   4.1 数据源
•     1) 真实数据集。
•     2) 合成数据集。
•   4.2 参数设置和实验环境
•   4.3 结果评测标准
•   4.4 实验结果与分析
•     1) 真实数据集上的结果分析。
•     2) 合成数据集上的结果分析。
•     3) 数据集更新时的性能分析。
• 5 结 语

文章来源

类型: 期刊论文

作者: 朱磊,姚燕妮,高勇,王一川,姬文江,黑新宏,刘征

关键词: 图挖掘,子图查询,最短权值路径,拉普拉斯图谱

来源: 西安理工大学学报 2019年03期

年度: 2019

分类: 工程科技Ⅱ辑,基础科学

专业: 数学

单位: 西安理工大学计算机科学与工程学院,西安理工大学自动化与信息工程学院

基金: 国家自然科学基金资助项目(61602374,61602376),陕西省自然科学基金资助项目(2016JQ6041,2017JQ6020),陕西省教育厅科研计划资助项目(16JK1552,16JK1573)

分类号: O157.5

DOI: 10.19322/j.cnki.issn.1006-4710.2019.03.004

页码: 291-299

总页数: 9

文件大小: 1568K

下载量: 52