一種改進(jìn)的RDF數(shù)據(jù)k—hop劃分算法

林培裕

摘要：RDF數(shù)據(jù)k-hop劃分算法是基于RDF大圖頂點劃分的算法，通過數(shù)據(jù)復(fù)制冗余以優(yōu)化分布式RDF查詢處理系統(tǒng)在特定SPARQL查詢模式下的查詢性能。針對算法可能會導(dǎo)致的數(shù)據(jù)傾斜及數(shù)據(jù)過量冗余問題，提出一種改進(jìn)的RDF數(shù)據(jù)k-hop劃分算法。該算法通過引入實體頂點的結(jié)構(gòu)與語義特征，將具有相似特征的圖頂點均勻分布到集群中，降低數(shù)據(jù)冗余量，提升算法的時間與空間性能。實驗結(jié)果表明，改進(jìn)后的算法是高效的。

關(guān)鍵詞：RDF；SPARQL；分布式系統(tǒng)；k-hop算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）01-0015-03

1 概述

隨著越來越多的項目與機(jī)構(gòu)采用RDF數(shù)據(jù)模型來表示它們的公共知識庫等靜態(tài)數(shù)據(jù)集，原先單節(jié)點式的RDF查詢處理系統(tǒng)已難以滿足海量數(shù)據(jù)的查詢需求，因此分布式RDF查詢處理技術(shù)已經(jīng)成為當(dāng)前語義網(wǎng)領(lǐng)域的一大重點。分布式RDF查詢處理一般包含數(shù)據(jù)劃分、查詢分解與子查詢中間結(jié)果合并三個階段[1]，其中數(shù)據(jù)劃分算法會在一定程度上影響網(wǎng)絡(luò)IO的開銷。k-hop數(shù)據(jù)劃分算法[2]通過數(shù)據(jù)復(fù)制冗余以優(yōu)化SPARQL查詢中的Star與Linear型模式[3]查詢，然而該算法沒有利用RDF數(shù)據(jù)本身的語義與圖結(jié)構(gòu)信息，導(dǎo)致劃分結(jié)果冗余較大且會產(chǎn)生數(shù)據(jù)傾斜。本文提出了一個k-hop算法的改進(jìn)方法，該方法能在一定程度上降低數(shù)據(jù)復(fù)制冗余量并提升查詢性能。

2 RDF數(shù)據(jù)k-hop劃分算法

RDF數(shù)據(jù)集中的每一條三元組都可以被看做是圖的一條邊，因此整個RDF三元組集形成了一張大圖，頂點即主體或客體，統(tǒng)稱為實體。k-hop算法是一個基于頂點哈希劃分的算法，具體過程如下：

1） 對于頂點集V中的所有實體進(jìn)行隨機(jī)哈希分配到機(jī)器中，，其中count為集群的機(jī)器個數(shù)；

2） 設(shè)，遍歷每臺機(jī)器上當(dāng)前頂點集，將與其中每個頂點連通且路徑長度在k之內(nèi)的頂點同樣復(fù)制到該機(jī)器上；

3） 遞增k，并重復(fù)步驟2），直到k大于預(yù)先設(shè)置的閾值；

4） 遍歷每臺機(jī)器上的最終頂點集，將以其中某個實體頂點為主體或客體的三元組分配到該機(jī)器上。

k-hop算法對長度在k之內(nèi)的Linear型SPARQL查詢模式較為友好，然而該算法需要對該長度閾值范圍內(nèi)的實體頂點進(jìn)行跨機(jī)器復(fù)制，數(shù)據(jù)冗余量較大，且前期的頂點哈希分配沒有考慮到頂點的語義與結(jié)構(gòu)特征，可能會導(dǎo)致嚴(yán)重的數(shù)據(jù)傾斜。

3 RDF圖頂點向量學(xué)習(xí)

針對k-hop算法沒有考慮到RDF數(shù)據(jù)的語義與圖結(jié)構(gòu)特征的問題，在頂點哈希分配之前引入一道新流程，提出基于SPARQL查詢模式的隨機(jī)游走模型，并通過該模型學(xué)習(xí)得到實體頂點的向量表示，以表征實體頂點的語義與結(jié)構(gòu)特征。

3.1 SPARQL查詢模式

一條SPARQL查詢語句可以由多條帶有變量的三元組構(gòu)成，根據(jù)變量的位置可以將SPARQL語句分解成多條如圖1所示的不同查詢模式[3]的子查詢語句。Star型查詢模式出現(xiàn)頻次較高，大多數(shù)的分布式RDF數(shù)據(jù)管理系統(tǒng)都會針對這種查詢模式進(jìn)行優(yōu)化。在將以RDF數(shù)據(jù)集中三元組的主體為中心頂點分布到不同機(jī)器上的同時，會將與相應(yīng)主體相連的客體同時劃分到與主體相同的機(jī)器上以滿足Star型查詢模式的需要。Linear型查詢模式可以被看做是以某一主體為起始點的深度優(yōu)先遍歷。Snowflake型查詢是由多條Star型查詢語句與一條連接各中心頂點的Linear型查詢語句組成，從圖遍歷的角度來說可以被看做是one-hop的廣度優(yōu)先遍歷。

3.2 基于查詢模式的有偏隨機(jī)游走模型

對于RDF有向圖以及隨機(jī)游走頂點序列，是游走過程中的第個頂點，是的相鄰頂點集合。與傳統(tǒng)隨機(jī)游走過程不同的是，將以一定的概率從中選取，而不僅僅是：

其中是對應(yīng)三元組的權(quán)重（大多數(shù)數(shù)據(jù)集中不含權(quán)重概念，默認(rèn)為1），是由頂點遍歷到的非標(biāo)準(zhǔn)轉(zhuǎn)移概率，以及是歸一化因子。轉(zhuǎn)移概率對隨機(jī)游走過程的頂點采樣會有較大的影響，如果恰好依次走過頂點和，則將會從或者中選擇，分別對應(yīng)了廣度優(yōu)先遍歷與深度優(yōu)先遍歷。比較直觀的確定該轉(zhuǎn)移概率值的方法是讓其與三元組的權(quán)重和成正比，然而這種辦法很難僅僅通過調(diào)整三元組權(quán)重來找到廣度遍歷與深度遍歷之間的折中點，從而不能很好的同時反映頂點之間在RDF圖中的結(jié)構(gòu)與語義上的相似度。因此兩個參數(shù)Linear型查詢模式權(quán)重與Snowflake型查詢模式權(quán)重被引入來引導(dǎo)游走偏向性。這兩個權(quán)重值能夠相對容易地從分布式RDF數(shù)據(jù)管理系統(tǒng)的查詢語句分解階段統(tǒng)計得到。轉(zhuǎn)移概率定義如下：

在某種意義上，參數(shù)控制了游走過程中離開當(dāng)前頂點并向深處探索的速率，而參數(shù)決定了徘徊于當(dāng)前頂點與周邊相鄰頂點的時間長短。當(dāng)時，游走過程退化為one-hop的廣度優(yōu)先遍歷，生成的游走路徑類似于Snowflake。經(jīng)多次迭代后從全局看類似于完整的廣度優(yōu)先遍歷，采樣生成的頂點序列能表現(xiàn)出頂點的局部結(jié)構(gòu)特征。當(dāng)時，游走過程則變成類深度遍歷的過程，主要表征出頂點的語義特征。因此通過調(diào)整這兩個參數(shù)值，我們的有偏隨機(jī)游走模型能夠為RDF圖上的深度優(yōu)先與廣度優(yōu)先遍歷間提供比較平滑的過渡過程。

3.3 實體頂點向量學(xué)習(xí)

給定RDF有向圖，將映射到低維向量空間的問題被稱為圖頂點向量學(xué)習(xí)。對于類似的問題，自然語言處理領(lǐng)域已經(jīng)有比較成熟的解決辦法，如word2vec的Skip-gram model。將上述隨機(jī)游走模型經(jīng)多次迭代后生成的路徑線性連接作為word2vec的輸入，同時調(diào)整滑動窗口大小參數(shù)以界定頂點的鄰接范圍。模型輸出的頂點向量表示可以從一定程度上反映頂點之間的結(jié)構(gòu)與語義相似度。

4 改進(jìn)的k-hop RDF數(shù)據(jù)集劃分算法endprint

4.1 基準(zhǔn)點集

考慮到分布式SPARQL查詢所需的高性能與均衡負(fù)載，在對RDF數(shù)據(jù)集進(jìn)行k-hop劃分之前，一種特殊的基準(zhǔn)點集需首先要被均勻劃分在集群中的不同機(jī)器上。基準(zhǔn)點的選擇對帶有復(fù)制三元組特性的RDF數(shù)據(jù)分布算法的劃分均衡性具有較大的影響。假設(shè)有兩臺機(jī)器的集群，對于子查詢語句，如果我們將選為基準(zhǔn)點，則部分如可能會被在多臺機(jī)器上復(fù)制。在此劃分基礎(chǔ)上，對于另一條子查詢語句，如果需要盡量降低兩條子查詢語句join期間機(jī)器內(nèi)部的通信開銷，也需隨在多臺機(jī)器上復(fù)制，這將造成嚴(yán)重的數(shù)據(jù)傾斜，然而將作為基準(zhǔn)點則不會形成這種情況。

在這里我們簡單地將連接度較大的頂點作為基準(zhǔn)點，主要是基于這樣的事實：隨機(jī)游走期間從任意兩個頂點出發(fā)相遇在連接度較大的頂點的概率較于其他頂點更大。因而如果這些連接度較大的頂點均勻分布在集群中，伴隨著將k-hop遍歷過程中遇到的頂點放置在同一機(jī)器上，則頂點集中的大部分點都會被涵蓋。這種劃分方式能有效減少k-hop算法的復(fù)制數(shù)據(jù)量，并降低數(shù)據(jù)傾斜的可能性。RDF圖中頂點的連接度與頂點的出入度密切相關(guān)，即與以某實體作為三元組主體或客體的頻次有著密切聯(lián)系。對于，設(shè)為頂點v的出入度和，為三元組中以v為主體的不同謂詞集合，為以v為主體的和p為謂詞的客體集合，則頂點v的連接度定義如下：

連接度計算示例如圖2所示。對于頂點s1，謂詞p1的分?jǐn)?shù)是（2+3）/2=2.5，謂詞p2的分?jǐn)?shù)是5，因此。RDF數(shù)據(jù)集中每個實體頂點的連接度值可以簡單的通過遍歷三元組集合統(tǒng)計得到。一般而言，連接度較高的頂點更容易被選為基準(zhǔn)點?；鶞?zhǔn)點集可以通過K-means算法得到?；谏弦还?jié)得到的實體頂點向量進(jìn)行聚類，生成的各聚類中的實體頂點在結(jié)構(gòu)與語義上相似，同時擁有最高平均連接度的實體頂點聚類可被選擇為基準(zhǔn)點集。

4.2 改進(jìn)算法流程

本文對傳統(tǒng)k-hop劃分算法的改進(jìn)思想就是將具有相似結(jié)構(gòu)與語義特征的實體頂點盡量均勻劃分到分布式集群中，并且優(yōu)先選擇基準(zhǔn)點集進(jìn)行劃分，以盡可能減少復(fù)制數(shù)據(jù)量以及數(shù)據(jù)傾斜的可能。算法的具體流程如下：

1） 遍歷RDF數(shù)據(jù)集三元組集合，計算實體頂點的連接度；利用word2vec學(xué)習(xí)得到實體頂點向量；

2） 根據(jù)實體頂點向量進(jìn)行K-means聚類，計算生成的各聚類的平均連接度，并從大到小進(jìn)行排序；

3） 選取聚類集合中平均連接度最大的聚類，利用隨機(jī)哈希將該聚類中的實體頂點均勻劃分到集群中，并將以該實體頂點為主體或客體的三元組劃分到同一機(jī)器上；

4） 利用k-hop算法對每一臺機(jī)器上的實體頂點集與三元組集進(jìn)行擴(kuò)展，并從各聚類中移除擴(kuò)展的實體頂點；

5） 將當(dāng)前使用的聚類從聚類集合中移除，重復(fù)3）至5）步驟，直至RDF數(shù)據(jù)集中所有的實體頂點與三元組集合被劃分到相應(yīng)機(jī)器上。

5 實驗與結(jié)果分析

本文實驗采用的數(shù)據(jù)集為LUBM標(biāo)準(zhǔn)測試集[4]。LUBM是一種標(biāo)準(zhǔn)RDF數(shù)據(jù)集生成器，可根據(jù)參數(shù)大學(xué)個數(shù)生成不同大小的標(biāo)準(zhǔn)測試數(shù)據(jù)集。本文分別選取大學(xué)個數(shù)為100、500、1000生成3個標(biāo)準(zhǔn)測試集，具體信息如表1所示。實驗采用的集群大小為包含6臺物理機(jī)器，每臺機(jī)器的配置為：Intel E5620處理器，16GB內(nèi)存及1TB 7200轉(zhuǎn)硬盤。

5.1 數(shù)據(jù)負(fù)載分布

如表2和表3所示為采用傳統(tǒng)k-hop算法與改進(jìn)算法時劃分的數(shù)據(jù)分布情況（經(jīng)統(tǒng)計分析，設(shè)置查詢模式參數(shù)以及k-hop算法參數(shù)可以達(dá)到最好的切分與查詢效果）?？梢钥闯?，傳統(tǒng)算法產(chǎn)生的分布結(jié)果的數(shù)據(jù)負(fù)載有一定的抖動，不如改進(jìn)算法的數(shù)據(jù)分布均勻，數(shù)據(jù)負(fù)載較重的存儲節(jié)點往往會成為分布式查詢處理過程中的瓶頸。同時，改進(jìn)算法產(chǎn)生結(jié)果的平均數(shù)據(jù)負(fù)載量要小于傳統(tǒng)算法，這能在一定程度上提升分布式SPARQL查詢性能。

5.2 查詢性能對比

本實驗選取LUBM1000測試集與前7個LUBM提供的SPARQL查詢語句進(jìn)行SHARD[5]、傳統(tǒng)k-hop算法與改進(jìn)算法實現(xiàn)的查詢系統(tǒng)（查詢分解與中間結(jié)果合并過程均相同[6]）的性能對比測試。對比結(jié)果如圖3所示，查詢耗費時間均為系統(tǒng)運行5次的平均值。從圖中可以看出，相比于SHARD系統(tǒng)，傳統(tǒng)k-hop與改進(jìn)算法都具有較大的性能優(yōu)勢，究其原因是SHARD將三元組集存儲為一個大HDFS文件，每次查詢都需要耗費大量的無用I/O操作，嚴(yán)重影響系統(tǒng)查詢性能。而k-hop算法將數(shù)據(jù)劃分后分別存儲在不同的機(jī)器上，I/O操作被分散，無需每次掃描完整的三元組數(shù)據(jù)集。同時，由于改進(jìn)算法較傳統(tǒng)k-hop算法擁有更小的復(fù)制數(shù)據(jù)量與更平衡的數(shù)據(jù)負(fù)載，查詢性能也較傳統(tǒng)算法有所提升。

6 結(jié)論

改進(jìn)算法和傳統(tǒng)k-hop算法擁有相同的時間復(fù)雜度并共享相同的查詢分解與中間結(jié)果合并流程。相比之下，通過添加向量學(xué)習(xí)和基準(zhǔn)點集選擇等流程降低了每臺機(jī)器上的數(shù)據(jù)量，數(shù)據(jù)分布更加均衡，相當(dāng)于降低了算法空間復(fù)雜度的常數(shù)因子，從而提高了查詢性能。

參考文獻(xiàn)：

[1] 杜方，陳躍國，杜小勇.RDF數(shù)據(jù)查詢處理技術(shù)綜述[J].軟件學(xué)報，2013（6）：1222-1242.

[2] Mikolov T， Sutskever I， Chen K. Distributed Representations of Words and Phrases and their Compositionality[J].Advances in Neural Information Processing Systems，2013（26）：3111-3119.

[3] Lee K， Liu L. Scaling queries over big RDF graphs with semantic hash partitioning[J]. Proceedings of the Vldb Endowment，2013，6（14）：1894-1905.

[4] Guo Y， Pan Z， He?in J. LUBM： A benchmark for OWL knowledge base systems[J]. Web Semantics Science Services & Agents on the World Wide Web，2005，3（23）：158-182.

[5] Rohloff K， Schantz R E. Clause-iteration with MapReduce to scalably query datagraphs in the SHARD graph-store[J].International Workshop on Data-Intensive Distributed Computing.ACM， 2011：35-44.

[6] Huang J， Abadi D J， Ren K. Scalable SPARQL querying of large RDF graphs[J].Proceedings of the Vldb Endowment，2011，4.endprint