动态描述逻辑推理的并行计算技术  

Parallel Computation Techniques for Dynamic Description Logics Reasoning

作　　者：王竹晓[1,2] 胡宏[1] 陈立民[1,2] 史忠植[1] 

机构地区：[1]中国科学院计算技术研究所智能信息处理重点实验室,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《计算机研究与发展》2011年第12期2317-2325,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60775035);国家"八六三"高技术研究发展计划基金项目(2007AA01Z132);国家"九七三"重点基础研究发展计划基金项目(2003CB317004;2007CB311004);国家科技支撑计划基金项目(2006BAC08B06)

摘　　要：在设计用于处理大规模本体和数据的推理引擎时,推理引擎的可扩展性是一个需要研究的重要问题.动态描述逻辑要在真实环境中获得成功应用,需要在推理中采用并行计算技术.提出了两种方法将并行计算技术应用于动态描述逻辑推理.方法1是设计分布式动态描述逻辑框架.分布式动态描述逻辑由若干独立的动态描述逻辑所组成,这些动态描述逻辑两两之间通过桥规则联系起来.提出了基于Tableau的分布式推理算法,从而为分布式动态描述逻辑提供了全局推理能力,并且该算法可以将大的推理任务分解为若干子任务,而这些子任务可以被不同的推理主体并行处理.方法2是并行化动态描述逻辑的Tableau算法的不确定分支.不确定分支的并行计算使得推理任务可以在若干独立机器上同时执行.最后,介绍了推理引擎的原型实现并评估了其性能.实验结果表明提出的两种方法取得了明显的推理加速效果.Scalability is an issue that needs to be considered when designing any reasoner for dealing with large and complex ontologies and large data sets. The practical usage of parallel computation techniques in reasoning is an important premise for the adoption of dynamic description logics （DDL） in a real-world setting. In this paper we describe two possible approaches for applying parallel computation techniques to DDL reasoning. The first approach is to design a logical framework of distributed dynamic description logics （D3L）, which is composed of a set of stand-alone DDLs pairwise interrelated with each other via collection of bridge rules. We present a tableau-based distributed reasoning procedure for providing the capability of global reasoning in D3L and decomposing large reasoning tasks to sub-tasks that could be concurrently processed by different reasoning agents. The second approach is to parallelize the nondeterministic branches within the DDL tableau procedure. The parallel computation of nondeterministic branches also makes it possible that the reasoning task is executed simultaneously on several independent machines. Finally, we introduce a prototype inference engine and present its evaluation. The results indicate that the proposed approaches achieve promising performance results.

关 键 词：并行推理 动态描述逻辑 分布式动态描述逻辑 表算法 推理引擎 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]