标签图的精确子图匹配算法研究

发布时间：2022-12-10 10:51

　　标签图作为一种重要的数据表示模型,广泛应用于生物化学、社交网络、知识图谱等领域,子图匹配作为图数据管理的一个重要操作,引起了研究者的普遍关注。本文针对标签图的子图匹配问题进行研究,分别给出了无重复标签图的子图匹配算法k~2-MDD-SubM和有重复标签图的子图匹配算法LCCP_SubM。本文的主要工作如下:（1）针对无重复标签图,引入k~2-MDD对其进行高效紧凑的表示以减小查询规模,同时结合符号计算的逻辑运算,给出一种子图匹配算法k~2-MDD-SubM,该算法将原始的子图匹配问题转化为基于k~2-MDD的布尔函数逻辑运算。以Graemlin和PPI数据集为例进行实验,对于Graemlin数据集,实验结果表明k~2-MDD-SubM所需存储的结点数仅为RI算法的35.83%,当模式图大小一定时,随着模式图密度的逐渐减小,算法的查询时间逐渐减少,且当模式图与目标图相同时,其查询效率优于RI算法。验证了k~2-MDD-SubM算法存储和查询性能的优越性;对于PPI数据集,实验结果表明k~2-MDD-SubM所需存储的结点数仅为RI算法的57.19%,同样随着模式图密度... 

【文章页数】：61 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    §1.1研究背景及意义
    §1.2国内外研究现状
    §1.3研究内容
    §1.4本文章节安排
第二章 相关知识介绍
    §2.1子图匹配相关知识
    §2.2子图匹配算法
    §2.3基于MDD的图数据表示方法k~2-MDD
        §2.3.1k~2-MDD定义与逻辑操作
        §2.3.2实验相关软件包
    §2.4本章小结
第三章 k~2-MDD-SubM：一种无重复标签图的子图匹配算法
    §3.1引言
    §3.2k~2-MDD-SubM算法
        §3.2.1无重复标签图的子图匹配定义
        §3.2.2k~2-MDD的构造
        §3.2.3k~2-MDD-SubM算法过程
        §3.2.4k~2-MDD-SubM的复杂度分析
    §3.3实验与分析
        §3.3.1数据集
        §3.3.2实验结果与分析
    §3.4本章小结
第四章 LCCP_SubM：一种有重复标签图的子图匹配算法
    §4.1引言
    §4.2变量排序
        §4.2.1变量排序特征
        §4.2.2变量排序策略
    §4.3LCCP_SubM算法过程
        §4.3.1LCCP_SubM中的变量排序
        §4.3.2约束过滤条件以及算法过程
        §4.3.3LCCP_SubM的复杂度分析
    §4.4实验与分析
        §4.4.1数据集
        §4.4.2实验结果与分析
    §4.5本章小结
第五章 结束语
    §5.1主要研究工作总结
    §5.2研究工作展望
参考文献
符号对照表
致谢
攻读硕士学位期间的主要研究成果


【参考文献】：
期刊论文
[1]动态图模式匹配技术综述[J]. 许嘉,张千桢,赵翔,吕品,李陶深.  软件学报. 2018(03)
[2]基于包含度的子图匹配方法[J]. 李瑞远,洪亮.  软件学报. 2018(06)
[3]ERSearch:一种高效的子图查询算法[J]. 黄云,洪佳明,覃遵跃,钟键,李梦婷,印鉴.  电子学报. 2017(02)
[4]大规模图数据的k~2-MDD表示方法与操作研究[J]. 董荣胜,张新凯,刘华东,古天龙.  计算机研究与发展. 2016(12)
[5]一种基于自适应结构概要的有向标签图子图匹配查询算法[J]. 张海威,解晓芳,段媛媛,温延龙,张莹,袁晓洁.  计算机学报. 2017(01)
[6]大规模图数据匹配技术综述[J]. 于静,刘燕兵,张宇,刘梦雅,谭建龙,郭莉.  计算机研究与发展. 2015(02)
[7]基于图数据挖掘算法的犯罪规律研究及应用[J]. 唐德权,张悦,贺永恒,肖自红.  计算机技术与发展. 2011(11)



本文编号：3716618