Spark GraphX上的SPARQL查询处理算法

摘要：

资源描述框架(resource description framework,RDF)由于其表示的灵活性和天然的图数据模型而变得越来越流行.与此同时,RDF数据的数据量也在以惊人的速度增长.由于数据量的增长,在单机上存储和查询RDF数据变得越来越不方便,从而激发了分布式存储查询的需求.学术界在分布式存储查询系统,例如Hadoop、Spark上已经做了大量的工作.基于Hadoop的分布式存储查询方式的主要缺点是中间结果需要被写回磁盘,从而产生大量的I/O操作.提出了一种新的在Spark GraphX上进行SPARQL查询评估的方法SQX,将RDF数据视为一个带标签的属性图,提出了一种新的查询计划生成方案并且通过图并行的方式实现SPARQL查询评估.SQX采用了一种"查询树匹配"+"结果过滤"的方法.针对每一个SPARQL查询,产生相应的查询树和约束条件.在每一轮的超级步中,查询树中的多条边可以被并行处理,对迭代执行完毕后的结果进行过滤,满足约束条件的将作为最终的结果.实验结果表明,算法能够有效处理SPARQL查询并且具有良好的可扩展性.

关键词：属性图、SPARQL查询、Spark GraphX、查询树

所属期刊栏目：12

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

资助基金：The National Natural Science Foundation of China under Grant Nos. 61672189, 61532015;the Program of Microsoft Key Laboratory of Natural Language Processing and Speech, Harbin Institute of Technology

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

页数：共11页

页码：1361-1371