陳 雙，汪璟玢

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

0 引言

近年來，隨著Linking Open Data和Wikipedia等項(xiàng)目的全面開展，使得Web 上的RDF數(shù)據(jù)量呈爆炸式增長[1]. 目前有關(guān)RDF上的關(guān)鍵詞搜索方法, 可分為兩類: 關(guān)鍵詞結(jié)構(gòu)化和關(guān)鍵詞直接匹配[2]. 第一種由關(guān)鍵字構(gòu)造結(jié)構(gòu)化查詢語句進(jìn)行查詢得到結(jié)果, 文獻(xiàn)[3-4]將關(guān)鍵字翻譯成聯(lián)合查詢, 再得到SPARQL查詢語句. Ladwig等[4]從RDF數(shù)據(jù)中抽取結(jié)構(gòu)信息，構(gòu)造結(jié)構(gòu)化查詢，然后查詢得到結(jié)果. 但這類方法實(shí)時(shí)響應(yīng)速度并不理想，時(shí)間開銷大, 執(zhí)行策略依賴于用戶的反饋，難以適應(yīng)大規(guī)模RDF數(shù)據(jù)存儲(chǔ)與搜索需求. 另一種關(guān)鍵詞直接匹配方法[5-6], 在圖數(shù)據(jù)上直接匹配包含所有查詢關(guān)鍵詞的子圖, 利用評分函數(shù)對候選答案排序，返回Top-k查詢結(jié)果. Le等[5]從RDF圖數(shù)據(jù)根據(jù)其類型抽取摘要信息，進(jìn)行剪枝從而加速搜索效率. 李慧穎等[7]將RDF數(shù)據(jù)建模成頂點(diǎn)帶標(biāo)簽的實(shí)體三元組關(guān)聯(lián)圖，利用斯坦納樹近似算法實(shí)現(xiàn)了快速查詢響應(yīng). 但都是集中式處理難以擴(kuò)展為分布式搜索，從圖中匹配關(guān)鍵詞的節(jié)點(diǎn)相對容易，確定節(jié)點(diǎn)之間的連接需要迭代地在圖上搜索. 因此，Virgilio[8]等提出一種新穎的完全分布式的RDF關(guān)鍵字搜索方法，預(yù)先存儲(chǔ)大量圖數(shù)據(jù)路徑索引，利用MapReduce 將圖并行問題轉(zhuǎn)換為數(shù)據(jù)并行處理問題，進(jìn)行高效的分布式搜索.

現(xiàn)存的分布式RDF數(shù)據(jù)查詢處理方案，集中于結(jié)構(gòu)化查詢SPARQL的研究，查詢規(guī)則復(fù)雜不能滿足普通用戶查詢需求，且難以適用于面向大規(guī)模RDF數(shù)據(jù)的關(guān)鍵詞搜索的場景. 因此，本研究提出一種面向大規(guī)模RDF數(shù)據(jù)的分布式關(guān)鍵詞搜索算法(KDSOS), 首先結(jié)合RDF本體構(gòu)造關(guān)鍵詞對應(yīng)的本體子圖集并利用評分函數(shù)評分，接著利用MapReduce計(jì)算框架分布式并行搜索，優(yōu)先按評分高的本體子圖連接生成查詢結(jié)果子圖，直至找到Top-k搜索結(jié)果.

1 相關(guān)定義

1.1 RDF數(shù)據(jù)模型

資源描述框架(resource description framework，RDF)是W3C推薦的用于在語義萬維網(wǎng)上表示信息的重要框架標(biāo)準(zhǔn)，通常采用 XML和三元組形勢來刻畫RDF，簡單易于掌握，可以靈活地表達(dá)數(shù)據(jù)語義. RDF數(shù)據(jù)集可由許多三元組構(gòu)成，其中每個(gè)三元組由主語(subject)、謂語(predicate)和賓語(object)3部分依次構(gòu)成. 把主語和賓語看作兩個(gè)點(diǎn)，謂語是由主語指向賓語的一條邊，那么一個(gè)RDF數(shù)據(jù)集可被看成一個(gè)有向標(biāo)記圖. 文中采用三元組形式表示RDF數(shù)據(jù)圖.

1.2 OWL本體

圖1 RDF本體圖片段Fig.1 Segment of RDF ontology graph

OWL(web ontology language)是W3C推薦的語義互聯(lián)網(wǎng)中本體描述語言的標(biāo)準(zhǔn)，由個(gè)體(individual)、屬性(property)和類(class)3部分組成. RDFS (RDF schema)是RDF圖數(shù)據(jù)的本體，定義類、屬性、類間及屬性間的關(guān)系，涵蓋了個(gè)體資源的分類及關(guān)聯(lián)關(guān)系. 圖1為數(shù)據(jù)集DBPedia[9]對應(yīng)的 RDF本體圖片段，其中實(shí)例類SpaceMission和實(shí)例類Rocket通過屬性booster關(guān)聯(lián)起來，屬性booster邊由SpaceMission指向Rocket.

1.3 相關(guān)定義

待解決的問題：給定關(guān)鍵詞查詢Q={q1,q2, …,qi, …,qm}，RDF數(shù)據(jù)圖G，返回Top-k搜索結(jié)果. 以下給出RDF關(guān)鍵詞搜索的相關(guān)定義.

定義1(RDF三元組) 設(shè)t〈s,p,o〉表示RDF三元組. 其中，s∈(IUB),p∈(IUB),o∈(IUBUL),I是URI頂點(diǎn)的集合，B是空白頂點(diǎn)集合，L是文本頂點(diǎn)集合.

定義2(RDF圖) 設(shè)G={t1,t2, …,ti, …,tn}表示RDF圖，一個(gè)RDF圖由一組RDF三元組定義.

圖2 類-屬性二維模型Fig.2 Class-property dimensional model

定義3(單元路徑, 記為p) 圖1等價(jià)轉(zhuǎn)換為圖2類-屬性二維模型(記為CP)，定義X-CP[X][Y]-Y為單元路徑，X、Y取值為實(shí)例類，CP[X][Y]取值為屬性，X與Y之間通過屬性關(guān)聯(lián)起來. 若實(shí)例類X和Y無關(guān)聯(lián)屬性，則為CP[X][Y]= ?. 通過單元路徑就可以直觀地表示出類與類、類與屬性間的關(guān)聯(lián)關(guān)系.

定義4(本體子圖, ontology subgraph) 設(shè)Gs={p1,p2, …,pi, …,pn}，一個(gè)本體子圖由n條單元路徑組成，其中任意兩個(gè)單元路徑pi=Xi-CP[Xi][Yi]-Yi和pj=Xj-CP[Xj][Yj]-Yj，通過X或Y或經(jīng)過其他單元路徑pk連接起來，即(Xi=Xj)或(Yj=Yi)或(Yi=Xj)或(Yj=Xi)或(pi-pk-pj). 一個(gè)本體子圖表示為一組單元路徑構(gòu)成的集合.

定義5(查詢結(jié)果，記為R) 設(shè)R= {t1,t2, …,tk, …,tr}，查詢結(jié)果是包含所有查詢關(guān)鍵詞頂點(diǎn)的一組三元組構(gòu)成的連通子圖，兩個(gè)三元組集合中元素不完全相同，則認(rèn)為是不同的查詢結(jié)果.

定義6(評分函數(shù)score estimation, 記為SE) 輸入查詢Q={q1,q2, …,qi, …,qm}，對應(yīng)RDF本體實(shí)例類C={c1,c2, …,ci, …,cm}，假定Q對應(yīng)的一個(gè)本體子圖Gsk={p1,p2, …,pi, …,pq}，其中pi=ch-CP[ch][cg]-cg，ch，cg∈C.

2 KDSOS算法

為了減小在大規(guī)模圖上迭代計(jì)算關(guān)鍵詞間連接路徑的開銷，方法先結(jié)合RDF本體圖為輸入關(guān)鍵詞構(gòu)建對應(yīng)的本體子圖集，然后利用SE評分函數(shù)進(jìn)行評分排序，最后在RDF數(shù)據(jù)圖上分布式搜索關(guān)鍵詞頂點(diǎn)按本體子圖連接關(guān)系進(jìn)行連接即可生成結(jié)果子圖，從而避免在大量數(shù)據(jù)圖頂點(diǎn)上直接迭代搜索頂點(diǎn)間連接路徑，提高搜索效率. KDSOS算法的總體框架設(shè)計(jì)如圖3所示.

圖3 KDSOS算法框架Fig.3 Algorithm framework of KDSOS

2.1 RDF分布式存儲(chǔ)模型

根據(jù)RDF圖數(shù)據(jù)的特點(diǎn)，同一類型的RDF實(shí)例三元組數(shù)據(jù)間的語義關(guān)系較密切. 實(shí)驗(yàn)借助分布式數(shù)據(jù)庫Hbase作為存儲(chǔ)媒介，依據(jù)類別進(jìn)行分布式存儲(chǔ)，具有關(guān)聯(lián)的同類數(shù)據(jù)存放一起. 具體Hbase表及存儲(chǔ)內(nèi)容說明:

OWL_Table表：存儲(chǔ)RDF本體信息，類、屬性的定義信息及關(guān)聯(lián)關(guān)系；

Index_S_Table表：主語S索引表, 存儲(chǔ)所有主語為S的實(shí)例三元組對應(yīng)類表

Index_O_Table表：賓語O索引表, 存儲(chǔ)所有賓語為O的實(shí)例三元組對應(yīng)的類表

ClassName_SPO表：存儲(chǔ)每個(gè)類的實(shí)例三元組信息，以(S, P, O)形式

ClassName_OPS表: 存儲(chǔ)每個(gè)類的實(shí)例三元組信息, 以(O, P, S)形式

其中，Index_S_Table和Index_O_Table是以S和O為主鍵的索引表，根據(jù)輸入查詢關(guān)鍵詞快速定位到對應(yīng)的具體實(shí)例類表ClassName_SPO或ClassName_OPS，幫助提高搜索效率.

2.2 構(gòu)建關(guān)鍵詞對應(yīng)本體子圖集

在2.1節(jié)基礎(chǔ)上，為用戶輸入查詢關(guān)鍵詞構(gòu)建本體子圖集. 首先確定各個(gè)查詢關(guān)鍵詞對應(yīng)本體中的實(shí)例類，構(gòu)建類-屬性二維模型CP，然后從中查找所有實(shí)例類對應(yīng)的單元路徑連接生成本體子圖集. 由于一個(gè)關(guān)鍵詞對應(yīng)的實(shí)例類可能存在多個(gè)或類間有多種關(guān)聯(lián)關(guān)系，因此一個(gè)查詢Q會(huì)存在多個(gè)本體子圖，通過SE函數(shù)評分排序. 算法1如下所示.

算法1:build-Gsk(Q,CP)輸入:關(guān)鍵詞查詢Q,Hbase數(shù)據(jù)表,CP輸出:本體子圖集按降序排列1. typeList←Q中m個(gè)查詢關(guān)鍵詞對應(yīng)實(shí)例類集2. H←?;//大小為k的大堆,堆中SE(Gs)≥SE(Gs’)3. Gs←?;//初始化4. forci∈typeList&i=1,2,…,m5. forcj∈typeList&j=1,2…,m{6. buildCP(CP,ci,cj);//構(gòu)建實(shí)例類ci,cj關(guān)聯(lián)路徑7. Gs.add(); 8. }9. //如果本體子圖Gs涵蓋所有關(guān)鍵詞實(shí)例類10. IfGscontainsallcintypeList11. if(SE(Gs)≥SE(Gs’))//Gs的語義評分大于H中下界12. H.push(Gs);13. //生成本體子圖集按降序排列14. End

舉例說明，輸入查詢關(guān)鍵詞“Apollo-11, Rocket, Armstrong”表達(dá)用戶想查詢關(guān)于“阿波羅11號”的信息. 為了便于解釋算法1執(zhí)行過程，如圖4所示，其中01, 02, 03和04分別表示關(guān)鍵詞對應(yīng)本體中實(shí)例類SpaceMission, string, Person和Rocket，CP[01][02]=name，CP[01][03]=crew, CP[01][04]=booster, CP[03][02]=name, 得到多個(gè)單元路徑連接生成一個(gè)本體子圖Gs1={p1,p2,p3,p4}，圖結(jié)構(gòu)表示見圖5.

圖4 搜索過程示例Fig.4 Process of search example

圖5 關(guān)鍵詞對應(yīng)的本體子圖Fig.5 Ontology sub-graph for query keywords

2.3 分布式并行搜索

借助MapReduce并行計(jì)算模型來完成分布式搜索. MapReduce處理過程包括Map階段與Reduce階段. 假定用戶輸入由m個(gè)關(guān)鍵詞構(gòu)成的查詢Q，其對應(yīng)RDF本體中的實(shí)例類集合C和匹配的關(guān)鍵詞頂點(diǎn)集合V. 執(zhí)行2.2節(jié)算法1，得到查詢Q對應(yīng)的本體子圖集Gs={Gs1, Gs2, …, Gsi, …, Gsk}. 一個(gè)本體子圖Gsi由多個(gè)單元路徑段構(gòu)成的，顯然Gs中不同本體子圖間有公共單元路徑，因此，在進(jìn)行MapReduce 計(jì)算前，先提取Gs所有本體子圖公共單元路徑，若Gs1和Gs2具有公共單元路徑{p1,p2}，記為〈(1, 2), (p1,p2)〉，保證公共單元路徑在搜索過程中只要計(jì)算一次.

Map階段:V和Gs作為Map的輸入，搜索本體子圖集中所有單元路徑對應(yīng)的實(shí)例三元組，若三元組滿足條件則生成一對〈key，value〉，key為對應(yīng)的本體子圖Gsi，value為四元組，如〈(Gsi), (p1,st,pt,ot)〉表示實(shí)例三元組(st,pt，ot)滿足本體子圖Gsi中一條單元路徑p1.

Reduce階段: Map的輸出作為Reduce的輸入，優(yōu)先按評分值高的本體子圖連接關(guān)系連接滿足條件的實(shí)例三元組，最后返回查詢Top-k結(jié)果Rs = {R1,R2, …,Ri, …,Rk}. 本研究方法只需開啟一個(gè)MapReduce任務(wù)就可以完成搜索. MapReduce分布式并行搜索過程如圖6所示.

Map階段Reduce階段Input:Q={q1,q2,…,qi,…,qm}Output:1. vertexList←m個(gè)關(guān)鍵詞匹配的關(guān)鍵詞頂點(diǎn)2. pathMap←關(guān)鍵詞頂點(diǎn)對應(yīng)單元路徑3. GsMap←單元路徑對應(yīng)本體子圖Gs4. forvi∈vertexListt&i=1,2,…,m5. pi=pathMap.get(vi);6. //單元路徑是否在本體子圖中7. if(Match(pi,Gsi)){8. Gsi=GsMap.get(pi); 9. output(>);10. }11. End;Input:Output:Alistofanswers1. Gsi←key2. ans←?;3. ansPath←?;4. forvalinvaluesdo5. //根據(jù)val值判斷對Gsi子路徑6. pi=val.get(0);7. triple=val.get(1);8. ansPath+=pi;9. ans.add(triple);10. Output(Gsi,triple);11. }12. ifansPath.equal(Gsi)13 Output(Gsi,ans);

圖6 MapReduce分布式搜索過程

Fig.6 Process of MapReduce distributed search

2.4 算法復(fù)雜度和完整性分析

2.4.1 算法復(fù)雜度分析

算法的時(shí)間復(fù)雜度包括兩部分構(gòu)建本體子圖集和MapReduce分布式搜索階段的時(shí)間復(fù)雜度. 假定用戶輸入關(guān)鍵詞個(gè)數(shù)M，關(guān)鍵詞映射后匹配類-屬性二維模型中單元路徑條數(shù)為N，生成的本體子圖個(gè)數(shù)為K，每條單元路徑匹配實(shí)例三元組條數(shù)為p，關(guān)鍵詞匹配的實(shí)例三元組條數(shù)為n. 下面列出這兩個(gè)階段最壞情況下的時(shí)間復(fù)雜性.

1) 構(gòu)建本體子圖集階段：O(N2×K).

2) 分布式搜索階段：Map階段的時(shí)間復(fù)雜度O(p)和Reduce階段的時(shí)間復(fù)雜度O(p×n×K).

綜上可知，KDSOS算法最壞情況下搜索一次的時(shí)間復(fù)雜度為O(N2×K) +O(p)+O(p×n×K). 相比于RDF數(shù)據(jù)圖規(guī)模的大小，N、K都非常小，而且搜索時(shí)通過類別進(jìn)行高效的過濾和匹配，每條單元路徑匹配到的實(shí)例數(shù)據(jù)p都是小規(guī)模且具有語義關(guān)聯(lián)的同類數(shù)據(jù)，因此算法整體時(shí)間復(fù)雜度近似常量級別. 算法的時(shí)間復(fù)雜性驗(yàn)證詳見3.2.1小節(jié)的對比實(shí)驗(yàn).

2.4.2 算法完整性分析

現(xiàn)有RDF關(guān)鍵詞搜索算法是基于圖搜索的思想，沒有考慮RDF語義信息，存在結(jié)果不全或不準(zhǔn)確的情況. 算法則充分利用RDF本體，通過將關(guān)鍵詞從內(nèi)容匹配映射到本體語義層面，將原本連接關(guān)系未知的關(guān)鍵詞通過本體進(jìn)行語義關(guān)聯(lián)起來. 在分布式搜索的階段，得到的本體子圖集作為MapReduce的一部分輸入，MapReduce階段只要完成數(shù)據(jù)并行搜索任務(wù)，并行搜索各個(gè)單元路徑匹配到的實(shí)例三元組按本體子圖進(jìn)行連接，就能夠精確返回與查詢關(guān)鍵詞匹配的結(jié)果子圖，從而保證查詢結(jié)果準(zhǔn)確性和完整性. 同時(shí)通過SE評分函數(shù)評分，優(yōu)先搜索高匹配的結(jié)果. 相比于現(xiàn)有的RDF關(guān)鍵詞搜索算法，算法具有與之相當(dāng)甚至更高的查準(zhǔn)率和查全率. 算法的完整性和正確性驗(yàn)證詳見3.2.1小節(jié)的對比實(shí)驗(yàn).

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

實(shí)驗(yàn)環(huán)境采用完全分布式Hadoop集群和Hbase分布式數(shù)據(jù)庫，由8個(gè)節(jié)點(diǎn)構(gòu)成，其中1個(gè)主節(jié)點(diǎn)，7個(gè)從節(jié)點(diǎn). 實(shí)驗(yàn)所使用的硬件環(huán)境為Intel(R) Core(TM) i5-3570，CPU 3.40GHz，內(nèi)存8 GB. 軟件環(huán)境為操作系統(tǒng)Linux Ubuntu，編程語言java，開發(fā)環(huán)境為Eclipse.

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為驗(yàn)證KDSOS方法的有效性，采用dblp[10]和DBpedia[9]兩個(gè)真實(shí)RDF數(shù)據(jù)集，與文獻(xiàn)[8]方法進(jìn)行了對比實(shí)驗(yàn). 表1列出10個(gè)有代表性的查詢示例, 分別包括1～5個(gè)關(guān)鍵詞, 第1組Q1～Q5用來測試dblp的查詢，第2組Q6～Q10用來測試DBpedia的查詢. 實(shí)驗(yàn)評價(jià)原則和結(jié)果的評測指標(biāo)參見第3.2節(jié).

表1 查詢關(guān)鍵詞

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

從開啟MapReduce任務(wù)數(shù)、搜索響應(yīng)時(shí)間、查準(zhǔn)率和查全率方面來分析實(shí)驗(yàn)結(jié)果，并在不同節(jié)點(diǎn)個(gè)數(shù)的集群和不同大小規(guī)模的數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)分析，驗(yàn)證算法具有良好的可擴(kuò)展性.

3.2.1 搜索響應(yīng)時(shí)間和正確性分析

圖7 查詢響應(yīng)時(shí)間對比 Fig.7 Comparison of response time

算法查詢時(shí)間包括構(gòu)建本體子圖集時(shí)間和分布式并行搜索時(shí)間，因?yàn)镽DF本體規(guī)模大小一般都為KB級別的(RDF本體中定義的類和屬性個(gè)數(shù)一般是幾百到千級別的)，構(gòu)建出查詢關(guān)鍵詞對應(yīng)的本體子圖集是很高效的，構(gòu)建時(shí)間<1 s. 查準(zhǔn)率(precision)用來衡量Top-k搜索結(jié)果的準(zhǔn)確率，指搜索結(jié)果中正確的條數(shù)與搜索結(jié)果總條數(shù)的比值. 查全率(recall)指搜索結(jié)果中正確的條數(shù)與數(shù)據(jù)集中相關(guān)的總條數(shù)的比值. 實(shí)驗(yàn)k值取10，查詢響應(yīng)時(shí)間取值為執(zhí)行10次查詢的平均值，查詢單位時(shí)間為秒(s). 對比實(shí)驗(yàn)結(jié)果如圖7～9所示，圖7～9中的查詢Q1～Q5是測試dblp數(shù)據(jù)集的查詢，查詢Q6～Q10為測試DBpedia數(shù)據(jù)集的查詢，Q1～Q10具體查詢關(guān)鍵詞如表1所示.

圖8 查準(zhǔn)率對比 Fig.8 Comparison of precision

圖9 查全率對比 Fig.9 Comparison of recall

通過對比實(shí)驗(yàn)發(fā)現(xiàn), 文獻(xiàn)[8]方法要開啟2個(gè)MapReduce任務(wù)，第一個(gè)任務(wù)處理產(chǎn)生可連接的路徑，第二個(gè)任務(wù)分析計(jì)算得到Top-k查詢結(jié)果. KDSOS方法需開啟的MapReduce任務(wù)數(shù)為1，有效地減少開啟多個(gè)MapReduce任務(wù)迭代處理消耗的時(shí)間. 分析圖7可知，KDSOS方法的查詢效率明顯優(yōu)于文獻(xiàn)[8]方法. 文獻(xiàn)[8]通過為RDF數(shù)據(jù)圖構(gòu)建大量的路徑索引幫助查詢，大量的圖路徑分布式在集群的不同節(jié)點(diǎn)，進(jìn)行查詢連接返回結(jié)果，MapReduce并行度大，網(wǎng)絡(luò)傳輸開銷大，因此查詢耗時(shí)較長. KDSOS方法通過本體子圖構(gòu)建關(guān)鍵詞KDSOS降低并行計(jì)算復(fù)雜度提高查詢效率. 分析圖8～ 9，查詢結(jié)果的查準(zhǔn)率和查全率與文獻(xiàn)[8]比，也具有一定優(yōu)勢. KDSOS方法基于RDF本體可以更好地查詢關(guān)鍵詞間語義關(guān)聯(lián)信息，SE評分函數(shù)有效地篩選出高匹配的本體子圖，縮小搜索范圍，從而提高查詢準(zhǔn)確率和搜索效率.

3.2.2 算法可擴(kuò)展性分析

為了驗(yàn)證KDSOS算法的擴(kuò)展性，在不同節(jié)點(diǎn)個(gè)數(shù)的集群和不同大小規(guī)模的數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如圖10、11所示. 圖10 是集群節(jié)點(diǎn)個(gè)數(shù)分別為4、6、8和10，測試數(shù)據(jù)集DBpedia的查詢Q6～Q10的響應(yīng)時(shí)間對比結(jié)果. 隨著集群節(jié)點(diǎn)增加，兩種方法的查詢響應(yīng)時(shí)間均有所增加，是因?yàn)楫?dāng)集群節(jié)點(diǎn)個(gè)數(shù)增加，開啟MapReduce任務(wù)時(shí)間會(huì)增加，且數(shù)據(jù)分布在不同節(jié)點(diǎn)導(dǎo)致節(jié)點(diǎn)間數(shù)據(jù)傳輸時(shí)間會(huì)增加，但文獻(xiàn)[8]方法的查詢時(shí)間增加更明顯. 因?yàn)槲墨I(xiàn)[8]方法需開啟多個(gè)任務(wù)，查詢連接并行度大，網(wǎng)絡(luò)傳輸開銷也大. 圖11 為DBpedia數(shù)據(jù)集從版本3.7，3.8到3.9數(shù)據(jù)規(guī)模不斷變大的情況下，執(zhí)行查詢Q6～Q10響應(yīng)時(shí)間的對比結(jié)果. 從圖11實(shí)驗(yàn)對比結(jié)果，可以看出KDSOS算法執(zhí)行查詢所需時(shí)間不會(huì)隨著數(shù)據(jù)量的倍數(shù)增大而增加倍數(shù)，增長近似平緩. 當(dāng)數(shù)據(jù)量增大時(shí)，方法的優(yōu)勢越能得到體現(xiàn)，這得益于通過本體子圖連接查詢關(guān)鍵詞頂點(diǎn)使查詢連接計(jì)算復(fù)雜度不會(huì)隨數(shù)據(jù)規(guī)模呈線性增長. 綜上所述，KDSOS算法具有良好的可擴(kuò)展性.

圖10 不同節(jié)點(diǎn)個(gè)數(shù)的集群下查詢響應(yīng)時(shí)間對比Fig.10 Comparison of response time on different cluster nodes

圖11 不同大小規(guī)模數(shù)據(jù)查詢響應(yīng)時(shí)間對比Fig.11 Comparison of response time on different scale data

4 結(jié)語

本研究提出結(jié)合RDF本體構(gòu)建本體子圖更好地查詢關(guān)鍵詞間語義關(guān)聯(lián)信息，減少在大規(guī)模圖數(shù)據(jù)上迭代連接計(jì)算的復(fù)雜度，實(shí)現(xiàn)面向大規(guī)模RDF數(shù)據(jù)的高效的分布式關(guān)鍵詞搜索. 同時(shí)定義評分函數(shù)，提高查詢關(guān)鍵詞與查詢結(jié)果匹配度，改進(jìn)搜索質(zhì)量. 后續(xù)研究工作將重點(diǎn)研究如何構(gòu)建有效地圖路徑索引，同時(shí)考慮緩存技術(shù)來幫助提高查詢效率并支持對動(dòng)態(tài)數(shù)據(jù)進(jìn)行搜索.

[1] KAOUDI Z, MANOLESCU I. RDF in the clouds: a survey[J]. The VLDB Journal, 2015, 24(1): 67-91.

[2] 杜方，陳躍國，杜小勇． RDF數(shù)據(jù)查詢處理技術(shù)綜述[J]． 軟件學(xué)報(bào)，2013，24(6)：1 222-1 242．

[3] ELBASSUONI S, RAMANATH M, SCHENKEL R,etal. Searching RDF graphs with SPARQL and keywords[J]. IEEE Data Eng Bull, 2010, 33(1): 16-24.

[4] LADWIG G, TRAN T. Combining query translation with query answering for efficient keyword search[M]//The Semantic Web: Research and Applications. Berlin: Springer, 2010: 288-303.

[5] LE W, LI F, KEMENTSIETSIDIS A,etal. Scalable keyword search on large RDF data[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(11): 2 774-2 788.

[6] ELBASSUONI S, BLANCO R. Keyword search over RDF graphs[C]//ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 237-242.

[7] 李慧穎, 瞿裕忠. KREAG: 基于實(shí)體三元組關(guān)聯(lián)圖的 RDF 數(shù)據(jù)關(guān)鍵詞查詢方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(5): 825-835.

[8] VIRGILIO R D, MACCIONI A. Distributed keyword search over RDF via MapReduce[M]//The Semantic Web: Trends and Challenges. [S.l.]: Springer, 2014: 208-223.

[9] AUER S, BIZER C, KOBILAROV G,etal. Dbpedia: a nucleus for a web of open data[M]. Berlin: Springer, 2007: 722-735.

[10] LEY M. DBLP: some lessons learned[J]. Proceedings of the VLDB Endowment, 2009, 2(2): 1 493-1 500.