林培裕

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

關鍵詞：RDF；SPARQL；分布式系統；k-hop算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）01-0015-03

1 概述

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

2 RDF數據k-hop劃分算法

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

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

2） 設，遍歷每臺機器上當前頂點集，將與其中每個頂點連通且路徑長度在k之內的頂點同樣復制到該機器上；

3） 遞增k，并重復步驟2），直到k大于預先設置的閾值；

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

k-hop算法對長度在k之內的Linear型SPARQL查詢模式較為友好，然而該算法需要對該長度閾值范圍內的實體頂點進行跨機器復制，數據冗余量較大，且前期的頂點哈希分配沒有考慮到頂點的語義與結構特征，可能會導致嚴重的數據傾斜。

3 RDF圖頂點向量學習

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

3.1 SPARQL查詢模式

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

3.2 基于查詢模式的有偏隨機游走模型

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

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

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

3.3 實體頂點向量學習

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

4 改進的k-hop RDF數據集劃分算法endprint

4.1 基準點集

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

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

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

4.2 改進算法流程

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

1） 遍歷RDF數據集三元組集合，計算實體頂點的連接度；利用word2vec學習得到實體頂點向量；

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

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

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

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

5 實驗與結果分析

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

5.1 數據負載分布

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

5.2 查詢性能對比

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

6 結論

改進算法和傳統k-hop算法擁有相同的時間復雜度并共享相同的查詢分解與中間結果合并流程。相比之下，通過添加向量學習和基準點集選擇等流程降低了每臺機器上的數據量，數據分布更加均衡，相當于降低了算法空間復雜度的常數因子，從而提高了查詢性能。

參考文獻：

[1] 杜方，陳躍國，杜小勇.RDF數據查詢處理技術綜述[J].軟件學報，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