面向大规模图数据的分布式子图匹配算法

摘要：

图数据规模的爆发式增长使在单机上的子图匹配变得较为困难.尽管现有的分布式算法可以在一定程度上解决大规模图数据的子图匹配问题,但分布式环境中的网络通信代价仍然影响着算法的性能.为此,文中提出了DS-search分布式子图匹配算法,包含查询图拆分、数据图预处理、候选顶点过滤、中间结果合并4个步骤.其中,在数据图预处理步骤中使用图划分和完善邻居顶点策略来降低匹配过程中分布式计算节点之间的通信代价;在过滤候选顶点阶段设计DSg raph存储结构存储候选顶点,通过推迟笛卡尔积来减少冗余的中间结果.最后设计了对比实验并在具有7个计算节点的Spark分布式集群上使用真实数据集进行验证.实验结果表明,DSsearch算法能够在秒级时间内完成对百万规模顶点的数据图的子图匹配,尤其是在处理复杂查询图和稠密数据图方面更高效.数据图预处理策略的实验结果说明了通过顶点复制来降低分布式环境中网络通信代价这一策略的可行性.相比TwinTwigJoin、PSgL等算法,随着查询图顶点数量的增加,DSsearch算法的运行时间增长得更缓慢,当查询图顶点数量达到14时,其运行时间是TwinTwigJoin和PSgL算法的一半.实验数据充分说明,分布式环境中的网络通信代价和中间结果数量是影响分布式子图匹配算法的主要因素.实现数据图的预处理和推迟笛卡尔积解决了分布式子图匹配的性能瓶颈问题,有效地完成了大规模图数据的子图匹配.

关键词：子图匹配、子图查询、分布式、图数据、图划分

所属期刊栏目：46

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61602427 ,山西省自然科学基金201601D202037

在线出版日期：2019-05-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：28-35