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

DPSM:Scalable efficient distributed subgraph matching method

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

The common subgraph matching algorithm has high complexity of time and space, and it is difficult to achieve largescale subgraph matching and to carry out distributed parallel and other problems, a distributed subgraph matching algorithm named DPSM was proposed. The query graph was split into several basic matching units, and these units were used to query in parallel. In this way, subgraph matching tasks of large scale directed graphs were solved efficiently. Besides, DPSM was implemented on Spark. Experimental results show that DPSM can accomplish subgraph matching tasks of graphs with over 100 million vertices and billions of edges in several seconds and performs well in scalability.