大规模RDF图数据上高效率分布式查询处理

知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(resourcedescriptionframework,简称RDF)形式发布出来.RDF图上的SPARQL查询语义对应于图同态,是一个NP-完全问题.因此,如何使用分布式方法在大规模RDF图上有效回答SPARQL查询是一个富有挑战性的问题.目前已有研究使用MapReduce计算模型处理大规模RDF数据,但其将SPARQL查询拆分成单个的查询子句,没有考虑RDF数据的丰富语义和自身的图特性,导致Map Reduce迭代次数过多.首先,利用RDF数据内嵌的语义和结构信息作为启发式信息,将查询图分解为星形的集合,可以在更少次迭代内得到查询结果.同时,分解算法给出中间结果较少的星形匹配顺序,基于此顺序,每轮Map Reduce操作通过连接操作匹配一个新的星形,直至产生最终的答案.最后,在标准合成数据集WatDiv和真实数据集DBpedia上进行大量的实验评估.实验结果表明:所提基于星形分解的分布式SPARQLBGP匹配算法能够高效回答查询,查询时间比SHARD和S2X算法的查询时间平均提高一个数量级,且优化算法的查询时间与基本算法相比缩短了49.63%～78.71%.

一种基于HBase的RDF数据存储模型

随着语义网数据的爆炸式增长,如何高效地管理海量RDF数据成为一个关键问题.现有的集中式关系型RDF数据存储管理系统已难以适应这种需求,越来越多的研究者使用分布式系统和并行计算技术来管理海量RDF数据.提出一种基于分布式数据库HBase的RDF数据存储模型,根据OWL本体定义文件,将数据按类划分,同一类的三元组数据保存在该类的S_PO和O_PS两张表中,实现该存储模型上的8种Triple Pattern和Basic Graph Pattern查询算法,并提供部分推理功能,在Hadoop集群环境下对存储模型与查询算法进行了可行性验证.

基于BSP的SPARQL基本图模式查询算法

随着语义网的不断发展,发布在互联网上的资源描述框架(RDF)数据达到百亿级三元组规模,并且呈现几何增长趋势,针对RDF数据的单机SPARQL查询方法已经不再适用。为此,提出一种基于整体同步并行(BSP)模型的SPARQL基本图模式查询算法。根据RDF有向图数据特性及基本图模式定义,将整个查询过程分成匹配和迭代2个阶段,在匹配出所需查询的三元组模式后,通过迭代使部分解逐步逼近完全解,得到最终查询结果。利用HAMA分布式计算框架进行算法实现,实验结果表明,与基于MapReduce的SPARQL查询算法相比,该算法具有较高的查询效率,能为大规模RDF数据的快速SPARQL查询提供支持。

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数据集上进行了性能实验.