基于Pregel编程模型的图模式匹配方法

发布时间：2020-03-25 00:51

【摘要】：图匹配是图数据应用的重要技术手段。与基于子图同构的匹配方法相比,图模拟放松了结构匹配要求,有效提升了图匹配效率。然而,对于大规模图数据上的图匹配而言,已有的基于模拟的图匹配方法仍然不能满足高效匹配的要求。针对这一问题,本文在已有的图模拟方法的基础上,提出了基于Pregel编程模型的并行化的图模拟匹配方法。本文的主要研究工作和贡献有以下几点:首先,针对“非圈”、“有圈”两种查询模式,分别提出了基于Pregel编程模型的并行化图模拟匹配方法。具体地给出了两种查询模式下,基于Pregel编程模型的:结点的消息初始化、结点消息响应和处理、消息合并、消息处理方法。其次,相关集是图匹配的重要质量度量指标。相关集的大小可以说明该模式在数据图上的覆盖度大小。针对“非圈”、“有圈”两种查询模式,分别提出了基于Pregel编程模型的并行化图匹配相关集求解方法。再次,基于Spark平台的并行计算机组件GraphX,实现了基于Pregel编程模型的图模拟匹配及相关集求解方法。最后,在真实数据集上,验证了本文提出基于Pregel编程模型的图模式匹配及相关集求解方法。实验结果表明在获得与已有方法相同匹配结果的情况下,本文的方法可明显缩短匹配时间,有效地提高了算法的匹配效率。
【图文】：

编程
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP311.13

【参考文献】