首页 > 笔记, 逻辑 > 笔记:描述逻辑的云计算(3)Liebig 2007

笔记:描述逻辑的云计算(3)Liebig 2007

Thorsten Liebig, Felix Müller: Parallelizing Tableaux-Based Description Logic Reasoning. OTM Workshops (2) 2007: 1135-1144 [bibtex]

This paper describes our approach for concurrent computation of the nondeterministic choices inherent to the standard tableau procedure.

Thorsten Liebig, Andreas Steigmiller and Olaf Noppens. Scalability via Parallelization of OWL Reasoning In Workshop on NeFoRS: New Forms of Reasoning for the Semantic Web: Scalable & Dynamic 2010

So far the design is tailored to a SMP (symmetric multi processor) architecture, where all processing cores have access to one main memory.

2007文目标逻辑是SHN,2010文目标是SHIQ(也就是增加inverse property and qualified number restriction)

主要利用树图算法中的不确定选择,例如disjunction rule或者at-most number restriction rule。这些选择会导致不同的ABox被产生。这些ABox被放在一个优先级队列(priority queue)里。初始ABox的优先级为0,n级ABox产生的ABox级别为n+1。

所谓ABox,其实就是Tableau。

本文没有具体讨论backtracking。如果一个ABox被发现inconsistent,是不是可以简单回到它的“父”ABox?

【构架】偷2010文图

【深入讨论】

所谓并行,就是要在尽可能减少通信代价的前提下,把操作分布到不同的处理器上去。在树图算法中,有几类很明显的可并行处理

  • 不确定选择(nondeterministic choices),例:A v B(x) -> A(x)或B(x)
  • 不同分支(branch)例:∃R.C ^ ∃R.D (x)  -> R(x,y), C(y)和R(x,z), D(z),则y和z两个分支可以分别处理。这一点在没有inverse property的时候成立。

有几类很明显的不适合并行处理

  • 远程计数(remote counting),例如A(x)在节点1,R(x,y)在节点2,R(x,z)在节点3,要问 =2R (x)是否成立,需要做两次远程查询。
  • 如果TBox本身是分布在不同节点上,而且需要远程连接时(remote join)

【分类】

一般做并行推理,大体是要么做数据的分布(distributed data),在树图算法里就是TBox的分布(ABox一定是分布的);要么做计算的分布(distributed computation),在triple-store里就是推理规则的分布,在树图算法里就是树图扩展的分布。如果TBox较小,可以由各节点共享TBox以减少通信代价。

模块化本体算法,将TBox分布,并改造语义以保证局域化(可以减少通信代价)。如果着眼于直接减少通信代价,可能有其他的DL子集,并不需要局域语义。

Liebig说,分布式推理有reasoner level的和proof level的。他的工作是proof level的。我的P-DL推理也是proof level的。DDL的推理是reasoner level的。

Reasoner level的实现比较容易,但是不能最充分的利用并行特性。

Advertisements
分类:笔记, 逻辑
  1. 还没有评论。
  1. 2012/04/16 @ 01:33

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: