论文部分内容阅读
近年来,随着语义网技术在众多领域的广泛应用,语义数据以惊人的速度迅速增长。大规模语义数据中包含了很多复杂的隐含信息,这些隐含信息对语义分析应用具有非常重要的价值。然而,传统的单机语义推理技术和算法由于受软硬件环境的限制已无法高效地处理大规模的语义数据。在此背景下,通过并行化技术解决大规模语义数据的推理问题成为新的研究热点。过去几年,一些并行化推理方法和系统不断地被提出,比如基于分布式哈希技术、基于P2P网络和基于MapReduce的分布式推理技术和算法等。然而,由于语义推理任务存在计算流复杂、数据共享重用频繁、迭代处理轮次多等特点,现有的并行化推理方案在处理大规模语义数据时在执行效率和可扩展性方面还存在较大的不足和缺陷。为了解决这些问题,本文在详细分析了主要的语义推理规则以及当前主流的并行化大数据计算系统和平台的基础之上,提出了一整套高效的语义推理并行化解决方案,设计并实现了一系列并行化的推理算法和系统。从推理规则的种类来看,具体研究工作主要分为以下两部分：1)并行化RDFS推理算法的研究。以语义网推理领域广为使用的RDFS规则推理为研究对象,分别从数据划分模型、规则执行次序、数据消重策略三个方面对RDFS推理并行化算法进行了优化设计,显著地提升了算法的执行效率。根据底层并行化计算平台的不同,设计并实现了两种RDFS并行化推理方案：基于MapReduce的并行化RDFS推理算法(YARM: Yet Another Reasoning System with MapReduce)和基于Spark的并行化RDFS推理算法(PRRS: A Parallel RDFS Reasoning System with Spark)。实验结果表明,在大规模Benchmark和真实数据集上,YARM和PRRS的执行速度比当前最快的基于MapReduce的推理引擎(reasoning-hadoop)快10倍以上,而且表现出了更好的数据和系统可扩展性。2)并行化OWL推理算法的研究。在RDFS推理算法的基础上,本文进一步研究了表达能力更强、逻辑更复杂、更广为使用的OWL Horst规则推理的并行化问题。针对OWL推理规则种类丰富、计算流复杂、迭代次数多、以及多趟计算任务间需要频繁共享和重用数据的问题,本文提出了一套基于Spark的并行化OWL推理技术和算法(PROS:A Parallel OWL Reasoning System with Spark)。PROS在4个方面对OWL推理进行了优化：1)在连接计算方面,采用广播变量和pre-shuffle优化技术,减少数据通信量,降低通信开销；2)在传递关系计算中,采用smart transitive closure算法减少迭代次数,提高执行效率；3)在owl:sameAs关系计算方面,采用统一表示技术,减少无用数据的产生,保证推理结果质量,提升计算速度；4)设计和实现了基于Spark的并行化OWL推理算法。实验结果表明,在大规模Benchmark和真实数据集上PROS的执行速度比当前最快的基于MapReduce的推理引擎快8-20倍左右,同时还表现出了良好的数据和系统可扩展性。