| 引用本文: | 张丽霞,王伟平,高建良,等.利用局部评估的分布式图模式匹配算法.[J].国防科技大学学报,2016,38(2):75-81.[点击复制] |
| ZHANG Lixia,WANG Weiping,GAO Jianliang,et al.A distributed graph pattern matching algorithm using partial evaluation[J].Journal of National University of Defense Technology,2016,38(2):75-81[点击复制] |
|
| |
|
|
| 本文已被：浏览 7564次 下载 6654次 |
| 利用局部评估的分布式图模式匹配算法 |
| 张丽霞1,2, 王伟平1, 高建良1, 王建新1 |
|
(1.中南大学 信息科学与工程学院， 湖南 长沙 410083;2.湖南师范大学 数学与计算机学院， 湖南 长沙 410081)
|
| 摘要: |
| 为了在分布式存储的大规模数据图上进行快速图模式匹配，提出利用局部评估的分布式图模式匹配算法。各计算节点并行地执行本地匹配；协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点；计算节点根据边界点的匹配状态确定与边界点相连的节点的匹配情况；协调器节点组合得出最大匹配集。实验结果表明：与已有的分布式图模式匹配算法相比，disGPM-PE算法都能够在不显著增加通信量的前提下避免数据片段间的依赖关系对执行时间的影响，从而减少图模式匹配的时间。 |
| 关键词: 图模式匹配 分布式算法 局部评估 |
| DOI：10.11887/j.cn.201602013 |
| 投稿日期：2015-03-27 |
| 基金项目:国家自然科学基金资助项目（61232001，61173169）；湖南省教育厅资助项目（15C0824） |
|
| A distributed graph pattern matching algorithm using partial evaluation |
| ZHANG Lixia1,2, WANG Weiping1, GAO Jianliang1, WANG Jianxin1 |
|
(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2.
2. School of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)
|
| Abstract: |
| 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. |
| Keywords: graph pattern matching distributed algorithms partial evaluation |
|
|
|
|
|
