StepMatch:一种基于BSP计算模型的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数据集上进行了性能实验.

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

所属期刊栏目：50

分类号：TP391(计算技术、计算机技术)

资助基金：国家“八六三”高技术研究发展计划基金项目2013AA013204;国家自然科学基金项目61100049,61070202,61373165

在线出版日期：2014-05-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：94-102