基于Spark的分布式并行推理算法①

葉怡新,汪璟玢

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州 350108)

基于Spark的分布式并行推理算法①

葉怡新,汪璟玢

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州 350108)

現(xiàn)有的RDF數(shù)據(jù)分布式并行推理算法大多需要啟動多個MapReduce任務(wù),有些算法對于含有多個實(shí)例三元組前件的OWL規(guī)則的推理效率低下,使其整體的推理效率不高.針對這些問題,文中提出結(jié)合TREAT的基于Spark的分布式并行推理算法(DPRS).該算法首先結(jié)合RDF數(shù)據(jù)本體,構(gòu)建模式三元組對應(yīng)的alpha寄存器和規(guī)則標(biāo)記模型;在OWL推理階段,結(jié)合MapReduce實(shí)現(xiàn)TREAT算法中的alpha階段;然后對推理結(jié)果進(jìn)行去重處理,完成一次OWL全部規(guī)則推理.實(shí)驗(yàn)表明DPRS算法能夠高效正確地實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的并行推理.

RDF;OWL;分布式推理;TREAT;Spark

語義萬維網(wǎng)中的RDF和OWL標(biāo)準(zhǔn)已在各個領(lǐng)域有著廣泛的應(yīng)用,如一般知識(DBpedia[1])、醫(yī)療生命科學(xué)(LODD[2])、生物信息學(xué)(UniProt[3])、地理信息系統(tǒng)(Linkedgeodata)和語義搜索引擎(Watson)等.隨著語義萬維網(wǎng)的應(yīng)用,產(chǎn)生了海量的語義信息.由于數(shù)據(jù)的復(fù)雜性和大規(guī)模性,如何通過語義信息并行推理高效地發(fā)現(xiàn)其中隱藏的信息是一個亟待解決的問題.由于語義網(wǎng)數(shù)據(jù)的急速增長,集中式環(huán)境的內(nèi)存限制,已不適用于大規(guī)模數(shù)據(jù)的推理.

研究RDFS/OWL分布式并行推理是目前較新的一個領(lǐng)域.J.Urbani[4-6]等人在RDFS/OWL規(guī)則集上采用WebPIE進(jìn)行推理,能夠滿足大數(shù)據(jù)的并行推理;但該算法針對每一條規(guī)則啟用一個或者多個MapReduce任務(wù)進(jìn)行推理,由于Job的啟動相對耗時(shí),因此隨著RDFS/OWL推理規(guī)則的增加,整體推理的效率受到了限制.顧榮[7]等人提出了基于MapReduce的高效可擴(kuò)展的語義推理引擎(YARM),使推理在一次MapReduce任務(wù)內(nèi)即可完成RDFS規(guī)則的推理;但該算法并不適用于復(fù)雜的OWL規(guī)則的推理.此外,當(dāng)某一規(guī)則產(chǎn)生的新三元組重復(fù)時(shí),YARM會存在過多的冗余計(jì)算且產(chǎn)生無用數(shù)據(jù).汪璟玢[8]等人提出結(jié)合Rete的RDF數(shù)據(jù)分布式并行推理算法,該算法結(jié)合RDF數(shù)據(jù)本體,構(gòu)建模式三元組列表和規(guī)則標(biāo)記模型;在RDFS/OWL推理階段,結(jié)合MapReduce實(shí)現(xiàn)Rete算法中的alpha階段和beta階段,從而實(shí)現(xiàn)Rete算法的分布式推理;但該算法在連接beta網(wǎng)絡(luò)推理時(shí)需要消耗較多的內(nèi)存且進(jìn)行多次迭代時(shí)效率低下,因而此算法受到集群內(nèi)存和平臺的限制.顧榮[9]等人提出了一種基于Spark的高效并行推理引擎(Cichlid),結(jié)合RDD的編程模型,優(yōu)化了并行推理算法;但該算法未考慮規(guī)則能否被激活,均需要進(jìn)行推理,因而造成了推理性能的浪費(fèi)和傳輸?shù)娜哂?

為了解決上述問題,本文針對OWL Horst規(guī)則,提出 了 DPRS算 法 (Distributed parallel reasoning algorithm based on Spark).該算法結(jié)合TREAT[10]算法和RDF數(shù)據(jù)本體構(gòu)建模式三元組的alpha寄存器RDD,預(yù)先對規(guī)則能否被激活做出判斷并標(biāo)記,僅對可激活的規(guī)則進(jìn)行推理的處理,實(shí)現(xiàn)在一個MapReduce任務(wù)中完成OWL全部規(guī)則的一次推理.最后,實(shí)時(shí)地刪除重復(fù)的三元組數(shù)據(jù)和更新沖突集數(shù)據(jù)到相應(yīng)的寄存器中,以進(jìn)一步提高后續(xù)迭代推理的效率.實(shí)驗(yàn)表明,該算法在數(shù)據(jù)量動態(tài)增加的情況下能夠高效地構(gòu)建alpha網(wǎng)絡(luò),并執(zhí)行正確的推理.

1 基本定義

定義1.模式三元組(SchemaTriple),指三元組的主語謂語和賓語都在本體文件(OntologyFile)中有定義.即:

其中,n表示模式三元組的總數(shù).若v∈{Si,Pj,Ok}, v∈OntologyFile,則:

定義2.實(shí)例三元組(InstanceTriple),指主語謂語和賓語至少有一個在本體文件(OntologyFile)中未定義,是具體的實(shí)例.即:

其中,n表示實(shí)例三元組的總數(shù).若v∈{Si,Pj,Ok},?v?OntologyFile,則:

定義3.三元組類型標(biāo)記(Flag_TripleType),用于標(biāo)識模式三元組與實(shí)例三元組,結(jié)合定義1和定義2,三元組類型標(biāo)記Flag_TripleType定義如下:

其中,n表示三元組的總數(shù).則:

定義4.模式三元組列表(SchemaRDD).用于獲取相同謂語或者賓語的模式三元組集合.結(jié)合定義1,模式三元組列表SchemaRDD定義如下:

其中,n表示模式三元組的總數(shù).則,

其中,Om_RDD表示滿足謂語Pj∈{rdf:type}且具有相同賓語的三元組集合,以該賓語命名;Pt_RDD表示滿足謂語Pj?{rdf:type}的所有具有相同謂語的三元組集合,以該謂語命名.具體定義如下:

定義 5.連接變量(LinkVar).連接變量為在RDFS/OWL規(guī)則中用于連接兩個前件的模式三元組項(xiàng),根據(jù)規(guī)則描述,連接變量可以不止一個.本文將每一條規(guī)則的連接變量信息以的形式存儲在Rulem_RDD,其中key存儲該規(guī)則所有用于前件連接的模式三元組項(xiàng),value存儲該規(guī)則結(jié)論部分的模式三元組項(xiàng).

DPRS算法根據(jù)連接變量的類型,對OWL Horst規(guī)則進(jìn)行分類.本文引用OWL Horst規(guī)則時(shí)采用OWL-規(guī)則編號的形式,例如OWL-4表示圖1中的第4條規(guī)則.同時(shí),給每條規(guī)則分配一個規(guī)則名稱標(biāo)記,規(guī)則名稱標(biāo)記即為該規(guī)則所對應(yīng)的名稱(例如,規(guī)則OWL-4的規(guī)則名稱標(biāo)記為OWL-4).具體的規(guī)則分類如下:

1)類型 1:只包含一個前件的規(guī)則或SchemaTriple與InstanceTriple組合的規(guī)則,且只有一個InstanceTriple,可以在Map推理過程中直接輸出推理結(jié)果(圖1中規(guī)則OWL-3、OWL-5a、OWL-5b、OWL-6、OWL-8a、OWL-8b、OWL-9、OWL-12a、OWL-12b、OWL-12c、OWL-13a、OWL-13b、OWL-13c、OWL-14a、OWL-14b).

2)類型2:SchemaTriple與InstanceTriple組合的規(guī)則,且有多個InstanceTriple的,需要結(jié)合 Map和ReduceByKey兩個階段推理(圖1中規(guī)則OWL-1、OWL-2、OWL-4、OWL-7、OWL-15、OWL-16).

定義 6.設(shè)Cmn為第m條規(guī)則的第n個模式三元組前件,定義規(guī)則前件模式標(biāo)記Indexmn, 用于標(biāo)識是否有符合該前件的模式三元組存在,即以該模式三元組前件Cmn所命名的SchemaRDD是否為空.結(jié)合定義4,規(guī)則前件模式標(biāo)記Indexmn定義如下:

定義7.規(guī)則標(biāo)記Flag_Rule_m,用于標(biāo)記該規(guī)則是否為不可能激活的規(guī)則.結(jié)合定義6進(jìn)行定義規(guī)則標(biāo)記Flag_Rulem如下:

Flag_Rulem={0,1,2}其中,規(guī)則不能激活時(shí),Flag_Rulem=0;規(guī)則激活且為類型1時(shí),Flag_Rulem=1;規(guī)則激活且為類型2時(shí), Flag_Rulem=2.

由于圖1中OWL規(guī)則5a、5b不影響推理的并行化,因而,本文所述推理不考慮這兩條規(guī)則.

圖1 OWLHorst規(guī)則

2 DPRS算法

在Rete算法中,同一規(guī)則連接結(jié)點(diǎn)上的寄存器保留了大量的冗余結(jié)果.實(shí)際上,寄存器中大部分信息已經(jīng)體現(xiàn)在沖突集的規(guī)則實(shí)例中.因此,如果在部分匹配過程中直接使用沖突集來限制模式之間的變量約束,不僅可以減少寄存器的數(shù)量,而且能夠加快匹配處理效率.這一思想稱為沖突集支撐策略.基于沖突集支撐策略,TREAT[10]算法放棄了Rete算法中利用β寄存器保存模式之間變量約束中間結(jié)果的思想.

DPRS算法根據(jù)Spark RDD的特點(diǎn),結(jié)合TREAT算法的原理,首先根據(jù)RDF本體數(shù)據(jù)構(gòu)建模式三元組對應(yīng)的alpha寄存器Om_RDD或Pt_RDD并廣播,然后對每條規(guī)則的模式前件進(jìn)行連接并生成對應(yīng)的連接模式三元組集合Rulem_linkvar_RDD,從而加快推理過程中的匹配速度,能夠?qū)崿F(xiàn)多條規(guī)則的分布式并行推理.DPRS算法主要包括以下幾個步驟:

Step1.加載模式三元組集合Pt_RDD、Om_RDD和Rulem_linkvar_RDD并廣播.

Step2.構(gòu)建規(guī)則標(biāo)記模型Flag_Rulem并廣播.

Step3.并行執(zhí)行OWL Horst規(guī)則推理.

Step4.刪除重復(fù)三元組.

Step5.如果產(chǎn)生新的模式三元組數(shù)據(jù),則跳至步驟Step2,如果產(chǎn)生新的實(shí)例三元組數(shù)據(jù),則跳至步驟Step3,否則跳至步驟Step6.

Step6.算法結(jié)束.

DPRS算法的總體框架圖如圖2所示.

圖2 DPRS算法總體框架圖

2.1 加載模式三元組與構(gòu)建規(guī)則標(biāo)記模型

由于模式三元組的數(shù)量遠(yuǎn)遠(yuǎn)少于實(shí)例三元組, DPRS算法將SchemaTriple加載到SchemaRDD中并廣播.并構(gòu)建每條規(guī)則中的模式三元組或模式三元組連接后的數(shù)據(jù)(Rulem_linkvar_RDD或 Om_RDD或Pt_RDD)為 alpha寄存器并廣播,保存對應(yīng)的SchemaTriple.

為了盡早判斷出不可能被激活的規(guī)則,DPRS算法根據(jù)OWL規(guī)則構(gòu)建每一條規(guī)則內(nèi)SchemaTriple間的關(guān)系Om_RDD或Pt_RDD,并判斷SchemaRDD中是否存在規(guī)則前件中的SchemaTriple,生成對應(yīng)規(guī)則的標(biāo)記Flag_Rulem,構(gòu)建所有規(guī)則的標(biāo)記模型,將規(guī)則標(biāo)記模型加載到Flag_Rulem并廣播.

通過SchemaRDD和構(gòu)建規(guī)則標(biāo)記模型能夠過濾大量InstanceTriple,減少M(fèi)ap階段鍵值對的輸出,從而減少了無效的網(wǎng)絡(luò)傳輸,提高整體推理效率.

2.2 Map階段

Map階段主要完成數(shù)據(jù)選擇過濾與類型1推理,將過濾的結(jié)果以鍵值對的形式輸出,本文提出的數(shù)據(jù)分配與過濾算法具體步驟如下:

Step1.獲取廣播變量中的Om_RDD、Pt_RDD和

Rulem_linkvar_RDD以及規(guī)則標(biāo)記Flag_Rulem.

Step2.對于輸入的?(Si,Pj,Ok)∈InstanceTriple判斷所有Flag_Rulem的值.如果值為0,則跳至Step3,如果值為1,則跳至Step4,否則跳至Step5.

Step3.對(Si,Pj,Ok)不做任何處理.

Step4.結(jié)合Om_RDD或Pt_RDD執(zhí)行類型1的規(guī)則推理,根據(jù)規(guī)則的結(jié)論直接輸出對應(yīng)的三元組

Step5獲取對應(yīng)規(guī)則中的模式三元組alpha寄存器Om_RDD、Pt_RDD或Rulem_linkvar_RDD,判斷當(dāng)前的實(shí)例三元組是否滿足前件連接變量的條件;滿足,則構(gòu)建對應(yīng)的鍵值對輸出;不滿足,則不做處理.

以圖1中規(guī)則8a(inverseOf)為例,偽碼描述如下:

類似于規(guī)則8,推理可以在Map階段就得到規(guī)則產(chǎn)生的三元組結(jié)果,那么reduce階段就可以對規(guī)則8產(chǎn)生的三元組去重并輸出.

以圖1中規(guī)則9(type+sameAs)為例,偽碼描述如下:

以圖1中規(guī)則15(someValuesFrom)為例,偽碼描述如下:

如上所描述的規(guī)則9和15,以規(guī)則9為例,在Map階段需要對輸入的三元組進(jìn)行處理,以“Rule9+連接變量”為key,如果謂語為type,那么value中標(biāo)記為type且資源為連接變量;如果謂語為sameAs,那么value中標(biāo)記為sameAs且資源為賓語.

2.3Reduce階段

Reduce階段主要完成連接推理.利用RDD的reduceByKey,結(jié)合OWL規(guī)則,根據(jù)SchemaRDD和alpha寄存器以及Map階段的InstanceTriple輸出結(jié)果完成連接推理,得到推理結(jié)果.本文提出的連接推理算法具體步驟如下:

Step1.獲取廣播變量中的Om_RDD、Pt_RDD和Rulem_linkvar_RDD以及規(guī)則標(biāo)記Flag_Rulem.

Step2.獲取相同鍵對應(yīng)的迭代器;如果key為Rulem,則表示為類型1,直接將value的三元組輸出;如果key為Rulem_linkvar,則表示為類型2,則根據(jù)該key對應(yīng)的OWL規(guī)則和連接變量,結(jié)合alpha寄存器Rulem_linkvar_RDD與value迭代器完成連接推理,得到推理結(jié)果并輸出連接后的三元組在執(zhí)行連接推理過程中,因?yàn)榉蠗l件的SchemaTriple已經(jīng)在構(gòu)建alpha寄存器時(shí)已連接完畢,所以只需要執(zhí)行SchemaTriple與InstanceTriple或InstanceTriple與InstanceTriple間的連接即可.

為了更加明確Reduce階段的連接推理,以圖1中規(guī)則9(type+sameAs規(guī)則)為例,偽碼描述如下:

以圖1中規(guī)則15(someValuesFrom規(guī)則)為例,偽碼描述如下:

由上述的規(guī)則9和規(guī)則15的偽碼,以規(guī)則9為例,在Reduce階段,根據(jù)輸入的key和values,我們通過values中的flag值來進(jìn)行區(qū)分并構(gòu)建輸出的三元組.

2.4 刪除重復(fù)三元組和沖突集更新策略

在執(zhí)行算法推理的過程中會產(chǎn)生大量重復(fù)的三元組數(shù)據(jù)到?jīng)_突集中,如不刪除沖突集中的重復(fù)三元組,則更新alpha寄存器時(shí)將會產(chǎn)生重復(fù)三元組數(shù)據(jù),浪費(fèi)系統(tǒng)資源,降低推理效率.如果每次推理后都能夠及時(shí)刪除沖突集中的重復(fù)三元組,那將會減少很大的網(wǎng)絡(luò)傳輸開銷.本文借助RDD的distinct和subtract完成刪除重復(fù)三元組算法.

通過上述的刪除重復(fù)三元組后,沖突集中的模式三元組分別更新到對應(yīng)的alpha寄存器中,實(shí)例三元組合則并到實(shí)例文件中.

2.5 算法的復(fù)雜度與完備性

復(fù)雜性分析是算法分析的核心,DPRS算法的復(fù)雜性與集中式算法復(fù)雜性的分析不太相同,將DPRS算法的最壞情況下的時(shí)間復(fù)雜性分為Map階段的時(shí)間復(fù)雜性和Reduce階段的時(shí)間復(fù)雜性.假設(shè)數(shù)據(jù)集的規(guī)模大小為N個三元組,其中模式三元組為n個,在MapReduce中Map階段的并行數(shù)為k,Reduce階段傳入的實(shí)例三元組個數(shù)為m,Reduce階段的并行數(shù)為t.

由于DPRS算法在Map階段對每個輸入的三元組,結(jié)合SchemaList、Flag_Rulem掃描一次,即可判斷該三元組是該舍棄或是能參與某些規(guī)則推理,如能參與后續(xù)規(guī)則推理,則以該規(guī)則名稱為key結(jié)合此三元組輸出.因此,Map階段的時(shí)間復(fù)雜性為:O(n*N/k).

由于圖1 OWL規(guī)則中,規(guī)則1、2、3、4、15、16都含有兩個實(shí)例三元組前件,將上述規(guī)則稱作多實(shí)例變量規(guī)則,多實(shí)例變量規(guī)則的Reduce階段則需要遍歷兩次輸入的實(shí)例三元組與模式三元組連接,才能得到推理結(jié)果.因此在Reduce階段的時(shí)間復(fù)雜性分為單變量和多變量進(jìn)行分析.

Reduce階段多變量的時(shí)間復(fù)雜性為:O(n*m/t).由于n的數(shù)目非常少,可以認(rèn)為其量級為常數(shù).

DPRS算法首先將數(shù)據(jù)集中的模式三元組載入內(nèi)存并廣播,根據(jù)定義7和OWL規(guī)則的描述構(gòu)建各個規(guī)則的Flag_Rulem,從而過濾掉不可能激活的規(guī)則.在能被激活的規(guī)則并行推理過程中的Map階段,對于輸入的一個三元組,DPRS判斷其是否滿足某個規(guī)則前件,只要滿足,就將此規(guī)則名稱作為鍵(key),值(value)為該三元組輸出;若一個三元組數(shù)據(jù)滿足多個規(guī)則前件,我們也將據(jù)此方法產(chǎn)生多個不同鍵(key)的輸出,以保障Reduce階段推理連接的正確性和數(shù)據(jù)完整性.如果Reduce階段產(chǎn)生的三元組去重后,有產(chǎn)生新的模式三元組,那么 DPRS算法將重新計(jì)算各個規(guī)則的Flag_Rulem,再執(zhí)行規(guī)則的并行推理迭代;如果Reduce階段產(chǎn)生的三元組去重后產(chǎn)生的是實(shí)例三元組,那么DPRS算法直接執(zhí)行規(guī)則的并行推理迭代,直到?jīng)]有新的三元組數(shù)據(jù)產(chǎn)生為止.因而DPRS算法所得到的推理結(jié)果是完備的.

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)所使用的軟件環(huán)境為操作系統(tǒng)Linux Ubuntu,采用scala作為編程語言,開發(fā)環(huán)境為IntelliJIDEA.在實(shí)驗(yàn)環(huán)境中,用表1所示配置作為本系統(tǒng)Spark集群的配置,共計(jì)8臺,其Hadoop集群中1臺作為HDFS的名稱節(jié)點(diǎn),1臺作為JobTracker節(jié)點(diǎn),6臺為HDFS的數(shù)據(jù)節(jié)點(diǎn)和TaskTracker節(jié)點(diǎn),Spark集群中1臺作為Master兼Worker節(jié)點(diǎn),7臺作為Worker節(jié)點(diǎn).集群工作站的基本配置如表1所列.

表1 Hadoop集群工作站的基本配置

本文將DPRS算法與DRRM[4]和Cichlid-OWL[9]在相同的實(shí)驗(yàn)環(huán)境下針對不同的數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn).本實(shí)驗(yàn)采用LUBM[11](Lehigh University Benchmark)數(shù)據(jù)集和DBpedia[1]數(shù)據(jù)集進(jìn)行測試.數(shù)據(jù)集的基本參數(shù)說明如表2所列.

表2 數(shù)據(jù)集的基本參數(shù)說明

我們將實(shí)驗(yàn)數(shù)據(jù)集中的模式三元組數(shù)進(jìn)行統(tǒng)計(jì)如表2所示,與整個數(shù)據(jù)集的大小相比,模式三元組的數(shù)量非常少,在所測試的數(shù)據(jù)集范圍內(nèi),模式三元組數(shù)目最高僅僅達(dá)到了整個數(shù)據(jù)集的0.04%.

表3 不同數(shù)據(jù)集三種算法在OWL推理產(chǎn)生的三元組數(shù)對比

表4 不同數(shù)據(jù)集三種算法在OWL推理時(shí)間對比

表5 DPRS算法在不同數(shù)據(jù)集上執(zhí)行推理的數(shù)據(jù)

從表3和表4可知,在OWL規(guī)則推理結(jié)果一致的情況下,DPRS比Cichlid-OWL具有優(yōu)勢.其中,由于LUBM數(shù)據(jù)集本體比較簡單,OWL Horst中的許多規(guī)則無法被激活,所以DPRS相比Cichlid-OWL的優(yōu)勢比較微弱;對于比較復(fù)雜的DBpedia本體而言,OWL的大部分規(guī)則都可被激活,由于本文使用了alpha寄存器廣播、連接變量、規(guī)則標(biāo)記和沖突集更新策略,使得DPRS算法的推理時(shí)間相對Cichlid-OWL算法最大縮短了21%的時(shí)間.

另外,DPRS與DRRM相比均有較大的優(yōu)勢.首先, DPRS使用Spark平臺比DRRM使用的Hadoop具有迭代性能優(yōu)勢;再者,DPRS采用沖突集更新策略,避免了beta網(wǎng)絡(luò)的開銷,大大減少了傳輸冗余造成的浪費(fèi).使得DPRS算法的推理時(shí)間相對DRRM算法最大縮短了73.8%的時(shí)間.

根據(jù)2.5節(jié)的復(fù)雜度分析,其中k和t為常數(shù),所以推理時(shí)間的復(fù)雜度與N和m成線性關(guān)系.結(jié)合表4和表5,考察數(shù)據(jù)集LUBM50和LUBM200,實(shí)例三元組個數(shù)N的比例為1:4.01,傳入Reduce的實(shí)例三元組數(shù)m的比例為1:3.89,推理時(shí)間的比例為1:4.20;考察數(shù)據(jù)集DBpedia3.7和DBpedia3.9,實(shí)例三元組個數(shù)N的比例為1:1.53,傳入Reduce的實(shí)例三元組數(shù)m的比例為1:1.41,推理時(shí)間的比例為1:1.35.可以發(fā)現(xiàn),我們的推理時(shí)間基本是與N和m成線性關(guān)系.從實(shí)驗(yàn)結(jié)果上符合了理論的分析,證明了算法的正確性.

從圖3和圖4可知,在執(zhí)行OWL規(guī)則推理時(shí),雖然兩種算法都需要多次迭代才能使得推理最終停止,但是DPRS在推理前構(gòu)建并廣播了模式三元組的alpha寄存器,并且在每次迭代中采用高效的過濾機(jī)制,過濾掉大量的實(shí)例三元組數(shù)據(jù),減少了并行計(jì)算量和網(wǎng)絡(luò)傳輸?shù)拈_銷,使得DPRS算法在最終的推理時(shí)間較Cichlid-OWL略占優(yōu)勢,尤其是在DBpedia數(shù)據(jù)集下,從表2中可以看出,Dbpedia的模式三元組占比相對LUBM高,且數(shù)據(jù)集較為復(fù)雜,其優(yōu)勢更加明顯.

圖3 采用未預(yù)處理與預(yù)處理算法在OWL推理的時(shí)間對比

圖4 采用過濾算法與未過濾算法產(chǎn)生的中間結(jié)果數(shù)目對比

由于在執(zhí)行推理過程中會產(chǎn)生重復(fù)的三元組數(shù)據(jù),重復(fù)三元組數(shù)據(jù)會造成系統(tǒng)資源無謂的浪費(fèi)并增加網(wǎng)絡(luò)的開銷.文中3.4節(jié)提出的刪除重復(fù)三元組算法,能夠減少重復(fù)的三元組數(shù)據(jù).為了評估算法的有效性,將刪除重復(fù)三元組前后的數(shù)據(jù)量進(jìn)行對比如圖5所示.刪除重復(fù)三元組后的三元組數(shù)量少于推理三元組數(shù)量,在所測試的數(shù)據(jù)范圍內(nèi).

圖5 刪除重復(fù)三元組前后三元組數(shù)量對比

4 結(jié)語

本文提出的 DPRS算法能夠通過執(zhí)行一次MapReduce任務(wù)就完成OWL所有規(guī)則的一次推理,彌補(bǔ)了現(xiàn)有方法大多需要啟動多個MapReduce任務(wù)以及在大規(guī)模數(shù)據(jù)下無法對OWL規(guī)則中含有實(shí)例三元組的規(guī)則進(jìn)行推理的問題.DPRS算法能夠在MapReduce計(jì)算框架下高效地實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的并行推理,但無法對流式數(shù)據(jù)進(jìn)行推理.下一步將會在此方面進(jìn)行改進(jìn),且研究更深一步的OWLDL推理.

1 Auer S,Bizer C,Kobilarov G,et al.Dbpedia:A nucleus for a web of open data.The Semantic Web.Springer Berlin Heidelberg.2007.722–735.

2 Jentzsch A,Zhao J,Hassanzadeh O,et al.Linking Open Drug Data.I–SEMANTICS.2009.

3 Apweiler R,Bairoch A,Wu CH,et al.UniProt:The universal protein knowledgebase.Nucleic AcidsResearch,2004, 32(s1):D115–D119.

4 Urbani J,Kotoulas S,Maassen J,et al.WebPIE:A web-scale parallel inference engine using MapReduce.Web Semantics: Science,Services and Agents on the World Wide Web,2012, (10):59–75.

5 Urbani J,Kotoulas S,Maassen J,et al.OWL reasoning with WebPIE:Calculating the closure of 100 billion triples. Extended Semantic Web Conference.SpringerBerlin Heidelberg.2010.213–227.

6 UrbaniJ.On web-scale reasoning[PhD.dissertation]. Amsterdam,Netherlands:Computer Science Department, Vrije Universiteit,2013.

7顧榮,王芳芳,袁春風(fēng),等.YARM:基于MapReduce的高效可擴(kuò)展的語義推理引擎.計(jì)算機(jī)學(xué)報(bào),2015,38(1):74–85.

8汪璟玢,鄭翠春.結(jié)合Rete的RDF數(shù)據(jù)分布式并行推理算法.模式識別與人工智能,2016,(5):5.

9 Gu R,Wang S,Wang F,et al.Cichlid:Efficient large scale RDFS/OWL reasoning with spark.Parallel and Distributed Processing Symposium(IPDPS),2015 IEEE International. IEEE.2015.700–709.

10 Miranker DP.TREAT:A new and efficient match algorithm forAI production system.Morgan Kaufmann,2014.

11 Guo Y,Pan Z,Heflin J.LUBM:A benchmark for OWL knowledge base systems.Web Semantics:Science,Services andAgents on the World Wide Web,2005,3(2):158–182.

Distributed Parallel ReasoningAlgorithm Based on Spark

YE Yi-Xin,WANG Jing-Bin

(College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China)

Multiple MapReduce tasks are needed for most of current distributed parallel reasoning algorithm for RDF data;moreover,the reasoning of instances of triple antecedents under OWL rules can’t be performed expeditiously by some of these algorithms during the processing of massive RDF data,and so the overall efficiency can’t be fulfilled in reasoning process.In order to solve the problems mentioned above,a method named distributed parallel reasoning algorithm based on Spark with TREAT for RDF data is proposed to perform reasoning on distributed systems.First step, alpha registers of schema triples and models for rule markup with the ontology of RDF data are built;then alpha stage of TREAT algorithm is implemented with MapReduce at the phase of OWL reasoning;at last,reasoning results are dereplicated and a whole reasoning procedure within all the OWL rules is executed.Experimental results show that through this algorithm,the results of parallel reasoning for large-scale data can be achieved efficiently and correctly.

RDF;OWL;distributed reasoning;TREAT;Spark

國家自然科學(xué)基金(61300104)

2016-09-21;收到修改稿時(shí)間:2016-10-31

10.15888/j.cnki.csa.005790