StepMatch:一种基于BSP计算模型的SPARQL基本图模式匹配算法

作     者：吕雪栋 冯志勇 王鑫 饶国政 付宇新 Lü Xuedong;Feng Zhiyong;Wang Xin;Rao Guozheng;Fu Yuxin

作者机构：天津大学计算机科学与技术学院天津300072 天津市认知计算与应用重点实验室天津300072 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2013年第50卷第S2期

页      面：94-102页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家"八六三"高技术研究发展计划基金项目(2013AA013204) 国家自然科学基金项目(61100049 61070202 61373165) 

主　　题：整体同步并行模型 消息传递 子图匹配 资源描述框架 SPARQL 

摘      要：随着语义网的发展,越来越多的数据通过资源描述框架(resource description framework,RDF)格式发布出来.目前有很多研究使用MapReduce计算模型处理大规模RDF数据,将SPARQL查询拆分成多步迭代.对于更适合使用消息传递模型来解决的图计算问题,MapReduce并非是最佳的选择.StepMatch算法基于整体同步并行(bulk synchronous parallel,BSP)计算模型,能有效解决SPARQL的基本图模式匹配查询.StepMatch是一个面向顶点的算法,RDF图中每一个顶点都被视为一个计算单元,顶点可以执行计算并向其他顶点发送消息.对于一个给定的SPARQL查询,StepMatch算法的超步数量与SPARQL查询包含的子句数目相等.最后,实现了StepMatch算法,并在合成的LUBM(Lehigh University Benchmark)数据集和真实的DBpedia数据集上进行了性能实验.