利用局部评估的分布式图模式匹配算法

A distributed graph pattern matching algorithm using partial evaluation

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

In order to execute graph pattern matching quickly in distributed large-scale graphs, an effective distributed algorithm using partial evaluation, namely disGPM-PE was proposed. Firstly, partial matching was performed locally at each computer nodes in parallel. Secondly, a coordinator node assembled the partial matching results, evaluated and sent 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 matching set was collected at the coordinator node. Experiment results show that the disGPM-PE algorithm can avoid the impact of the dependent relations between data fragments on the execution time. Compared with the previous distributed graph pattern matching algorithms, the disGPM-PE algorithm can reduce the execution time of graph pattern matching while do not increase the network traffic obviously.