DPSM:可扩展高效的分布式子图匹配方法

摘要：

为解决当前常见的子图匹配算法具有较高时间空间复杂度、难以实现大规模子图匹配和难以进行分布式并行等问题,提出一种可扩展高效的分布式子图匹配方法DPSM.将查询图拆分为基本匹配单元,使用基本匹配单元分布式并行查询,以数据并行方式有效解决大规模有向图子图匹配任务.在Spark平台上实现DPSM系统,实验结果表明,DPSM能够在秒级时间完成拥有上亿顶点、数十亿边的大规模自然图子图匹配任务,具有良好的可扩展性.

关键词：子图匹配、查询图、数据图、分布式、高效索引

所属期刊栏目：38

分类号：TP391.9(计算技术、计算机技术)

资助基金：国家自然科学基金项目61003076

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

页数：共6页

页码：2161-2166