利用局部评估的分布式图模式匹配算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金资助项目(61232001,61173169);湖南省教育厅资助项目(15C0824)


A distributed graph pattern matching algorithm using partial evaluation
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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. 

    参考文献
    相似文献
    引证文献
引用本文

张丽霞,王伟平,高建良,等.利用局部评估的分布式图模式匹配算法[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.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-03-27
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2016-05-06
  • 出版日期:
文章二维码