计算机应用

作者：李龙洋, 董一鸿, 施炜杰, 潘剑飞

单位：1. 宁波大学 信息科学与工程学院, 浙江 宁波 315211;2. 北京百度在线科技有限公司, 北京 100084

关键词：子图匹配,图分割,大规模单图,并行化,Spark

基金：国家自然科学基金资助项目（61572266）；浙江省自然科学基金资助项目（LY16F020003）；宁波市自然科学基金资助项目（2017A610114）。

针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题，为提高查询准确率，降低大图下的查询开销，提出一种基于Spark的子图匹配（SQM）算法。首先根据结构信息过滤数据图，再将查询图分割成基本查询单元；然后对每一个基本查询单元分别匹配后进行Join操作；最后运用并行化提高了算法的运行效率，减小了搜索空间。实验结果表明，与Stwig、TurboISO算法相比，SQM算法在保证查询结果不变的情况下，速度提高了50%。

来源：2019年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第1期