基于局部评估的分布式图模式匹配算法

为了在分布式存储的大规模数据图上进行快速图模式匹配，提出了基于局部评估的分布式图模式匹配算法disGPM-PE。首先各计算节点并行地执行本地匹配，然后协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点，接着计算节点根据边界点的匹配状态确定与边界点相连的节点的匹配情况，最后协调器节点组合得出最大匹配集。实验结果表明：与已有的分布式图模式匹配算法相比，disGPM-PE算法都能够在不显著增加通信量的前提下避免数据片段间的依赖关系对执行时间的影响，减少了图模式匹配的时间。

A distributed algorithm based on partial evaluation to graph pattern matching

In order to execute graph pattern matching quickly in distributed large-scale graphs, an effective distributed algorithm based on partial evaluation which is named disGPM-PE is proposed. Firstly, partial matching is performed locally at each computer nodes in parallel. Secondly, a coordinator node assembles the partial matching results, evaluates and sends the matching conditions of boundary nodes to corresponding computer nodes. Thirdly, each computer nodes determines the matching conditions of the nodes connected to the boundary nodes. Finally, the maximum match is collected at the coordinator node. The experiment results show that disGPM-PE can avoid the impact of the dependent relations between data fragments on the execution time. Compared with the previous distributed graph pattern matching algorithms, disGPM-PE can reduce the execution time of graph pattern matching while do not increase the network traffic obviously.