MPPIE:基于消息传递的RDFS并行推理框架

随着语义Web的快速发展,RDF(resource description framework)语义数据规模呈现爆炸性增长趋势,大规模语义数据上的推理工作面临严峻挑战。基于消息传递机制提出了一种新的RDFS(RDF schema)并行推理方案。利用RDF图数据结构,建立RDFS推理过程的图上加边模型。以顶点为计算中心,根据不同推理模型,向其他顶点传递推理消息,完成推理操作。当所有推导出的新三元组以边的形式加入原RDF图中时,整个推理过程结束。在基于消息传递模型的开源框架Giraph上,实现了RDFS并行推理框架MPPIE(message passing parallel inference engine)。实验结果表明,在标准数据集LUBM和真实数据集DBpedia上,MPPIE执行速度均比当前性能最好的语义推理引擎Web PIE快一个数量级,且展现了良好的可伸展性。

基于嵌套正则表达式的RDF图数据属性路径查询及推理

SPARQL 1.1引入的属性路径查询提供了大规模RDF图数据上进行路径查询的支持.现有的属性路径查询实现方案均基于多重索引,经过多次迭代查询实现,效率低下,且只能对显式的RDF三元组进行查询,不具备推理能力.嵌套正则表达式可以支持全部的RDFS推理,并在多项式时间复杂度内执行路径查询.因而,将属性路径查询转化为嵌套正则表达式的求值,可以提高查询效率,挖掘隐藏信息.实现了RDFS-Plus原型系统,包括属性路径查询的解析器和基于嵌套正则表达式的查询引擎,采用基于自动机的图算法,避免了求RDF图闭包.最后,提供了与ARQ和Sesame的对比实验.实验表明,提出的基于嵌套正则表达式的RDF图数据属性路径查询方法不仅可以支持推理,而且维持了多项式的计算复杂度.

基于迭代MapReduce的大规模RDF本体传递推理方法研究

随着Web内容爆炸式增长,基于RDF的开放关联数据越来越多,传统的RDF推理技术难以适应日益增长的大规模RDF数据推理任务.提出基于MapReduce的分布式迭代算法,设计了简洁的去重方法,实现分布式RDF推理,解决了RDF传递推理工程中持续产生单调递增数据集传递闭包问题.实验采用基于Hadhoop的分布式文件系统存储MapReduce算法,实验结果显示方法具有较好的计算性能和可扩展性.

YARM:基于MapReduce的高效可扩展的语义推理引擎

随着语义网的快速发展,RDF语义数据大量涌现.大规模RDF语义数据推理的一个主要问题是计算量大、完成计算需要消耗很长的时间.显然,传统的单机语义推理引擎难以处理大规模的语义数据.另一方面,现有的基于MapReduce的大规模语义推理引擎,缺乏对算法在分布和并行计算环境下执行效率的优化,使得推理时间仍然较长.此外,现有的推理引擎大多存在可扩展性方面的不足,难以适应大规模语义数据的增长需求.针对现有的语义推理系统在执行效率和可扩展性方面的不足,文中提出了一种基于MapReduce的并行化语义推理算法和引擎YARM.为了实现分布和并行计算环境下的高效推理,YARM做出了以下4点优化:(1)采用合理的数据划分模型和并行化算法,降低计算节点间的通信开销;(2)优化推理规则的执行次序,提升了推理计算速度;(3)设计了简洁的去重策略,避免新增作业处理重复数据;(4)设计实现了一种新的基于MapReduce的并行化推理算法.实验结果表明,在真实数据集和大规模合成数据集上,YARM的执行速度比当前最新的基于MapReduce的推理引擎快10倍左右,同时YARM还表现出更好的数据和系统可扩展性.