陳志奎 ，冷泳林 ，2

1.大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116620 2.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000

雙目標(biāo)優(yōu)化的RDF圖分割算法

陳志奎1，冷泳林1，2

1.大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116620 2.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000

分布式存儲(chǔ)是解決大規(guī)模數(shù)據(jù)存儲(chǔ)的一種比較有效的方法，而數(shù)據(jù)分割是實(shí)現(xiàn)分布式存儲(chǔ)的前提。面對(duì)不斷增長(zhǎng)的RDF數(shù)據(jù)，提出一種基于雙目標(biāo)優(yōu)化的RDF圖分割算法（RDF Graph Partitioning algorithm based on Double Objective Optimization，RGPDOO）。RGPDOO將邊割和分割平衡兩項(xiàng)圖分割指標(biāo)融合到一個(gè)目標(biāo)函數(shù)，并依據(jù)此目標(biāo)函數(shù)，實(shí)現(xiàn)了RDF圖的靜態(tài)和動(dòng)態(tài)分割。其中靜態(tài)圖分割通過(guò)對(duì)圖進(jìn)行初始劃分，將圖中頂點(diǎn)分成內(nèi)核頂點(diǎn)、交叉頂點(diǎn)和自由頂點(diǎn)三類(lèi)。然后通過(guò)計(jì)算目標(biāo)函數(shù)增益對(duì)交叉和自由頂點(diǎn)進(jìn)行分配。動(dòng)態(tài)圖分割部分，針對(duì)RDF元組的插入和刪除給出相應(yīng)的解決方案。同時(shí)，為了滿(mǎn)足圖分割目標(biāo)，算法每隔一段時(shí)間T會(huì)根據(jù)子圖的平衡性和緊密性進(jìn)行一次動(dòng)態(tài)調(diào)整。實(shí)驗(yàn)選擇合成和真實(shí)數(shù)據(jù)集進(jìn)行測(cè)試，并分別與幾種通用的靜態(tài)和動(dòng)態(tài)圖分割算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明提出的算法能夠有效地實(shí)現(xiàn)RDF圖的靜態(tài)和動(dòng)態(tài)分割。

RDF圖；靜態(tài)分割；動(dòng)態(tài)分割；邊割；負(fù)載均衡

1 引言

萬(wàn)維網(wǎng)聯(lián)盟（W3C）推薦的資源描述框架（Resource Description Framework，RDF）是描述語(yǔ)義網(wǎng)中各種資源與它們之間語(yǔ)義關(guān)系的一個(gè)重要框架標(biāo)準(zhǔn)[1]。RDF使用三元組〈主語(yǔ)，謂語(yǔ)，賓語(yǔ)＞來(lái)描述世界，當(dāng)把主語(yǔ)和賓語(yǔ)看做圖中兩個(gè)頂點(diǎn)，謂語(yǔ)看做是由主語(yǔ)指向謂語(yǔ)的有向邊時(shí)，RDF數(shù)據(jù)集可以被看做是一個(gè)有向圖。隨著Link Open Data（LOD）[2]和DBpedia等項(xiàng)目的全面展開(kāi)，語(yǔ)義Web的數(shù)據(jù)量不斷增加，大量RDF數(shù)據(jù)被發(fā)布。

面對(duì)大規(guī)模RDF數(shù)據(jù)，傳統(tǒng)單機(jī)模式已經(jīng)不能滿(mǎn)足數(shù)據(jù)存儲(chǔ)需求。數(shù)據(jù)分布式存儲(chǔ)是目前公認(rèn)地解決大規(guī)模數(shù)據(jù)存儲(chǔ)比較有效的方法。而實(shí)現(xiàn)分布式存儲(chǔ)的前提就是如何有效對(duì)數(shù)據(jù)進(jìn)行分割。尤其是RDF圖本質(zhì)特征，使數(shù)據(jù)之間存在大量關(guān)聯(lián)。如果分割不當(dāng)，就會(huì)導(dǎo)致查詢(xún)時(shí)，存儲(chǔ)節(jié)點(diǎn)之間產(chǎn)生大量通信。另外，分割平衡性也將影響數(shù)據(jù)并行執(zhí)行的效率。并且，RDF數(shù)據(jù)是不斷更新變化的，要保持良好的分割狀態(tài)，對(duì)應(yīng)的數(shù)據(jù)分割算法就應(yīng)該具有適應(yīng)數(shù)據(jù)變化的能力。

基于以上分析，本文提出一種雙目標(biāo)優(yōu)化的RDF圖分割算法（RDF Graph Partitioning algorithm based on Double Objective Optimization，RGPDOO）。算法以最小化邊割和分割平衡作為RDF圖分割目標(biāo)設(shè)計(jì)了一個(gè)雙目標(biāo)優(yōu)化函數(shù)。并基于此目標(biāo)函數(shù)實(shí)現(xiàn)了RDF數(shù)據(jù)的靜態(tài)和動(dòng)態(tài)圖分割算法。實(shí)驗(yàn)中，本文選擇RDF標(biāo)準(zhǔn)數(shù)據(jù)集從邊割、分割效率和分割平衡三方面驗(yàn)證算法的有效性。實(shí)驗(yàn)結(jié)果表明，本文提出的雙目標(biāo)函數(shù)從邊割和平衡兩方面保證RDF圖數(shù)據(jù)分割的質(zhì)量，有效地實(shí)現(xiàn)RDF圖的靜態(tài)和動(dòng)態(tài)分割。

文中其他部分內(nèi)容概括如下：第2章介紹RDF圖分割相關(guān)工作；第3章詳細(xì)闡述雙目標(biāo)函數(shù)的設(shè)計(jì)；第4章描述了雙目標(biāo)函數(shù)下RDF圖的靜態(tài)和動(dòng)態(tài)分割算法；最后通過(guò)實(shí)驗(yàn)驗(yàn)證RGPDOO算法的性能并得出結(jié)論。

2 相關(guān)工作

近年來(lái)，隨著RDF數(shù)據(jù)的廣泛應(yīng)用，關(guān)于RDF圖分割算法的研究也越來(lái)越多。SPA[3]采用頂點(diǎn)中心塊兒的分割機(jī)制對(duì)RDF圖進(jìn)行分割。VB-Partitioner[4]擴(kuò)展了SPA思想，在其基礎(chǔ)上對(duì)頂點(diǎn)中心塊兒進(jìn)行n跳擴(kuò)展，來(lái)避免查詢(xún)時(shí)節(jié)點(diǎn)間的通信。BRGP專(zhuān)門(mén)針對(duì)RDF圖中頂點(diǎn)的不對(duì)稱(chēng)關(guān)系以及圖的冪率特性提出基于模塊度的標(biāo)簽傳播算法對(duì)圖進(jìn)行粗化分割。Wu[5]等人提出了一種基于路徑的圖分割算法，算法將RDF圖分解成由源點(diǎn)到匯點(diǎn)所組成的路徑，然后再以路徑為單位進(jìn)行分割。Huang等人將METIS圖分割框架直接應(yīng)用于RDF數(shù)據(jù)分割，通過(guò)副本方式降低SPARQL查詢(xún)中各分區(qū)之間的通信[6]。Wang等人利用標(biāo)簽傳播算法對(duì)RDF圖頂點(diǎn)進(jìn)行粗化，并結(jié)合METIS對(duì)粗化圖進(jìn)行分割[7]。以上這些算法都是基于靜態(tài)RDF圖進(jìn)行分割，并沒(méi)有給出圖動(dòng)態(tài)變化時(shí)的解決方案。

朱牧等人提出基于密度的增量聚類(lèi)算法可以實(shí)現(xiàn)圖的增量分割，但該算法主要傾向于社交網(wǎng)絡(luò)中重疊社區(qū)發(fā)現(xiàn)問(wèn)題，并沒(méi)有考慮圖分割的邊割和平衡兩項(xiàng)分割指標(biāo)[8]。Fennel是一種基于流的圖分割框架，該框架在目標(biāo)函數(shù)地限制下結(jié)合一定的啟發(fā)式算法來(lái)實(shí)現(xiàn)圖分割[9]。張曉媛[10]等人提出的基于鄰域動(dòng)態(tài)圖分割算法NDA在靜態(tài)圖分割的基礎(chǔ)上，按照不同的圖數(shù)據(jù)增長(zhǎng)方式，根據(jù)存儲(chǔ)節(jié)點(diǎn)最小負(fù)載原則或KNN原則進(jìn)行節(jié)點(diǎn)的遷移或添加。該算法在動(dòng)態(tài)圖分配階段只考慮負(fù)載均衡來(lái)轉(zhuǎn)移不平衡節(jié)點(diǎn)，并沒(méi)有考慮邊割問(wèn)題。Martella[11]等人提出的Spinner是一種基于標(biāo)簽傳播的增量圖分割算法，Spinner在Pregel分布式圖計(jì)算平臺(tái)基礎(chǔ)上將標(biāo)簽傳播算法擴(kuò)展成為一種分布式的圖分割算法，保證分割算法的可擴(kuò)展性。Spinner能夠根據(jù)圖和計(jì)算環(huán)境的變化自動(dòng)調(diào)整圖分割結(jié)果，避免圖的重新分割。在處理增量節(jié)點(diǎn)時(shí)，Spinner通過(guò)重啟迭代的方式，讓全局頂點(diǎn)都參與到最優(yōu)計(jì)算中，雖然獲得了一個(gè)很好的分割結(jié)果，但這種方式非常耗時(shí)。SPAR[12]以最小化副本為分割目標(biāo)將社交網(wǎng)絡(luò)中每個(gè)用戶(hù)所有相關(guān)信息劃分到一個(gè)存儲(chǔ)節(jié)點(diǎn)來(lái)保證分割局部語(yǔ)義完整性。并且針對(duì)節(jié)點(diǎn)、邊和存儲(chǔ)節(jié)點(diǎn)的添加刪除給出了圖的自適應(yīng)分割策略。Sedge[13]提出了補(bǔ)充和按需兩種分割技術(shù)，并依據(jù)這兩種技術(shù)，創(chuàng)建了一個(gè)具有兩層分割結(jié)構(gòu)的圖分割架構(gòu)：主要分割和輔助分割，來(lái)處理變化的圖查詢(xún)。Xu等人提出的LogGP[14]將圖和歷史分割結(jié)構(gòu)結(jié)合到一起，構(gòu)成一個(gè)超圖，并且利用基于超圖的流分割方法得到初始分割。在分割過(guò)程中，還會(huì)依據(jù)運(yùn)行時(shí)的統(tǒng)計(jì)信息評(píng)估每個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間，對(duì)后繼執(zhí)行做出動(dòng)態(tài)調(diào)整。以上這些算法在圖的動(dòng)態(tài)分割方面做出了貢獻(xiàn)，但這些算法并沒(méi)有針對(duì)RDF圖特征及其分割目標(biāo)給出合適的解決方案。

3 雙目標(biāo)優(yōu)化函數(shù)的設(shè)定

給定一個(gè)RDF圖G=(V,E)，其中V表示圖中頂點(diǎn)集合，E表示圖中的邊集，|V|=n和|E|=m分別表示圖中頂點(diǎn)和邊的數(shù)目。一個(gè)k路圖分割就是將RDF圖分成 k個(gè)不相連接的子圖 P={G1,G2,…,Gk}，其中Gi={Vi,Ei},i=1,2,…,k是一個(gè)分割子圖。當(dāng) i≠j時(shí)，Vi∩Vj=φ并且

邊割和平衡性是衡量圖分割質(zhì)量的兩項(xiàng)重要指標(biāo)，其中邊割是指連接兩個(gè)不同子圖之間邊。子圖之間邊割越小，表示它們之間的聯(lián)系越稀疏，數(shù)據(jù)并行執(zhí)行時(shí)彼此之間需要交換的信息越少，數(shù)據(jù)并行性越高。本文用inter(Gi,Gj)表示子圖Gi和Gj之間的邊割，則：

當(dāng)來(lái)自?xún)蓚€(gè)不同子圖的頂點(diǎn)a和b之間存在連接，則e(a,b)為1，否則為0。同邊割相對(duì)應(yīng)，用intra(Gi)表示任意一個(gè)子圖內(nèi)部邊的數(shù)目，本文定義為內(nèi)割，則：

顯然，一個(gè)子圖的內(nèi)割越高，子圖內(nèi)部節(jié)點(diǎn)之間關(guān)系越緊密，即子圖獨(dú)立性越強(qiáng)。

圖分割的平衡性是指各分割子圖中頂點(diǎn)的數(shù)目趨于相等。在分布式系統(tǒng)中各存儲(chǔ)節(jié)點(diǎn)硬件環(huán)境相同情況下，各子圖頂點(diǎn)規(guī)模越趨于相等，系統(tǒng)并行執(zhí)行的效率越高。當(dāng)任意一個(gè)分割子圖Gi中頂點(diǎn)數(shù)目滿(mǎn)足公式（3）時(shí)，圖分割P趨于平衡。其中e是一個(gè)介于0和1之間的浮動(dòng)因子，即允許圖規(guī)模在一定范圍內(nèi)浮動(dòng)。

由以上分析，圖分割不僅要最小化邊割，而且還要保證分割子圖的平衡性。為此，本文提出一個(gè)基于邊割和平衡的雙目標(biāo)函數(shù) f(P),f(P)滿(mǎn)足：

其中cut(P)代表圖分割的邊割，對(duì)于一個(gè)k路圖分割P，cut(P)滿(mǎn)足：

其中：

balance(P)代表圖分割的平衡性，balance(P)滿(mǎn)足：

綜上，當(dāng)雙目標(biāo)函數(shù) f(P)取最小值時(shí)，圖分割結(jié)果最優(yōu)。但圖分割是一個(gè)NP-完全問(wèn)題，要得到精確分割結(jié)果是很困難的。因此目標(biāo)是尋找一個(gè)近似最優(yōu)解。為實(shí)現(xiàn)這一目標(biāo)，對(duì) f(P)做如下處理。

給定一個(gè)函數(shù)g(P)，如公式（8）所示：

由公式（4）、（8）和（9）可得：

當(dāng)求 f(P)的最小值時(shí)，對(duì)應(yīng)就是求g(P)的最大值。因此，在確定一個(gè)頂點(diǎn)v所屬分區(qū)時(shí)，可以通過(guò)計(jì)算?g(P,i,v)的最大增益值來(lái)確定。

如圖1，設(shè)n/k=4，兩個(gè)分割子圖G1和G2的 g(p)當(dāng)前值為7。當(dāng)新節(jié)點(diǎn)i分別加入到子圖G1和G2時(shí)，g(p)的值為7和8，則產(chǎn)生的增益值分別為?g(P ,G1,i)=1和?g(P ,G2,i)=0，因此選擇G2分區(qū)。從圖1中也可以直觀看出，加入G2所產(chǎn)生的邊割要小于G1，而平衡性的變化是一致的。

圖1 計(jì)算最大增益值

4 基于雙目標(biāo)函數(shù)的RDF圖分割算法

基于以上目標(biāo)函數(shù)，本章給出兩種不同狀態(tài)RDF圖分割算法。第一種是針對(duì)已經(jīng)存在的靜態(tài)RDF圖，另一種是針對(duì)變化的RDF圖給出的動(dòng)態(tài)分割方案。

4.1 靜態(tài)圖分割

本文基于雙目標(biāo)函數(shù)，改進(jìn)了k路貪婪圖分割算法（Improved k-way Greedy Graph Growing Partitioning，IKGGGP）[15]，實(shí)現(xiàn)了對(duì)靜態(tài)RDF圖的分割。不同于KGGGP算法，IKGGGP算法首先對(duì)RDF圖進(jìn)行初始劃分，將圖中頂點(diǎn)劃分成只屬于一個(gè)分區(qū)的內(nèi)核頂點(diǎn)；存在于多個(gè)分區(qū)的交叉頂點(diǎn)和不屬于任何分區(qū)的自由頂點(diǎn)。對(duì)于內(nèi)核頂點(diǎn)，它們只屬于一個(gè)唯一分區(qū)，無(wú)需再進(jìn)行分配。而交叉頂點(diǎn)和自由頂點(diǎn)，IKGGGP通過(guò)計(jì)算目標(biāo)函數(shù)的最大增益值為它們選擇合適分區(qū)。

4.1.1 初始劃分

SPARQL查詢(xún)本質(zhì)是子圖匹配問(wèn)題，如果將緊密聯(lián)系的節(jié)點(diǎn)分配到同一分區(qū)，將極大地降低查詢(xún)時(shí)存儲(chǔ)節(jié)點(diǎn)之間的通信。當(dāng)圖中頂點(diǎn)同其鄰域具有很大相似性時(shí)，這個(gè)頂點(diǎn)更容易成為圖中的一個(gè)核心頂點(diǎn)。本文就從圖中的k個(gè)核心頂點(diǎn)開(kāi)始向外擴(kuò)展，對(duì)RDF圖進(jìn)行初始劃分。經(jīng)過(guò)初始劃分的圖中存在一類(lèi)特殊頂點(diǎn)，它們是只與分區(qū)內(nèi)的頂點(diǎn)有關(guān)聯(lián)的內(nèi)核頂點(diǎn)。如圖2所示的紅色頂點(diǎn)即是內(nèi)核頂點(diǎn)。內(nèi)核頂點(diǎn)只屬于一個(gè)分區(qū)，因此一旦初始區(qū)域劃分結(jié)束，這些頂點(diǎn)的分區(qū)也就固定，不需要在進(jìn)行分區(qū)選擇。

給定一個(gè)RDF圖，Γ(v)是頂點(diǎn)v的鄰域集合。Γε(v)表示頂點(diǎn)v的鄰域中與v的相似度大于或等于閾值ε的頂點(diǎn)集合。如果|Gε(v)|的鄰域數(shù)目超過(guò)閾值δ，稱(chēng)頂點(diǎn)v是圖中的一個(gè)核心頂點(diǎn)。

在尋找RDF圖中核心頂點(diǎn)時(shí)需要計(jì)算頂點(diǎn)v與其鄰域頂點(diǎn)的相似性。傳統(tǒng)地計(jì)算圖節(jié)點(diǎn)相似性的方法都是基于頂點(diǎn)的結(jié)構(gòu)信息，如隨機(jī)游走[16]、計(jì)算公共鄰域[17]等方法。本文由于RDF圖是一個(gè)語(yǔ)義圖，節(jié)點(diǎn)間存在一定的語(yǔ)義關(guān)系。如果將語(yǔ)義上聯(lián)系緊密的頂點(diǎn)劃分到一個(gè)分區(qū)，將更有利于查詢(xún)的并行執(zhí)行。因此本文提出了一種基于語(yǔ)義的頂點(diǎn)相似性度量方法。

RDF采用統(tǒng)一資源標(biāo)識(shí)符（Uniform Resource Identifier，URI）來(lái)標(biāo)識(shí)圖中的頂點(diǎn)和邊。URI通過(guò)目錄結(jié)構(gòu)體現(xiàn)圖中頂點(diǎn)所屬類(lèi)、超類(lèi)及節(jié)點(diǎn)信息。如果圖中兩個(gè)頂點(diǎn)所屬公共超類(lèi)越多，說(shuō)明它們的相似性就越大，即這兩個(gè)頂點(diǎn)聯(lián)系越緊密。用函數(shù)sup(v)來(lái)計(jì)算頂點(diǎn)v所屬超類(lèi)，則衡量?jī)蓚€(gè)頂點(diǎn)u和v的語(yǔ)義相似性，如公式（11）所示：

當(dāng)某一個(gè)頂點(diǎn)只有一個(gè)入邊，則它與指向它的頂點(diǎn)的相似性為1。當(dāng)確定圖中核心點(diǎn)后，就可以對(duì)圖進(jìn)行初始劃分了。算法1給出了初始劃分的偽代碼。

算法1初始劃分

輸入 核心頂點(diǎn)集core,圖G

輸出 初始劃分P={G1,G2,…,Gk}

方法：

Initialqueue(q)；p＜—1；//初始化隊(duì)列q和分區(qū)編號(hào)

Do while p＜=k

v〈—select(core)；//從核心頂點(diǎn)集隨機(jī)選擇一個(gè)頂點(diǎn)

remove(core,v)；//從核心頂點(diǎn)集移除v

inqueue(q,v)；//頂點(diǎn)v入隊(duì)列

i＜—1；

partition(v)＜—p；//為頂點(diǎn)分配分區(qū)編號(hào)和分區(qū)內(nèi)序號(hào)

number(v)＜—i；

i＜—i+1；Gp=Gp?v；

Do while not isempty(q)andi＜n/k

v＜—outqueue(q)；

for each u in Γε(v)do

ifu∈core

remove(core,u)；

ifu?Gp

inqueue(q,u)；

partition(u)＜—p；

number(u)＜—i；

ifi=n/k

exit for

i＜—i+1；Gp=Gp?u；

end for

end do

p=p+1；

clearqueue(q)；//清空隊(duì)列

end do

4.1.2 交叉頂點(diǎn)和自由頂點(diǎn)分配

當(dāng)RDF圖經(jīng)過(guò)初始分割后，內(nèi)核頂點(diǎn)的分區(qū)已經(jīng)確定。除了內(nèi)核頂點(diǎn)，初始分割結(jié)果中還存在兩類(lèi)頂點(diǎn)，如圖2中紫色的交叉頂點(diǎn)和藍(lán)色的自由頂點(diǎn)（統(tǒng)稱(chēng)為待分配節(jié)點(diǎn)），需要計(jì)算它們所屬分區(qū)。本文通過(guò)計(jì)算函數(shù)g(P)的最大增益值，來(lái)確定這兩類(lèi)頂點(diǎn)的分區(qū)，即：

圖2 RDF圖分區(qū)的核心頂點(diǎn)

IKGGGP算法中待分配頂點(diǎn)分配執(zhí)行步驟如下：

步驟1計(jì)算所有待分配頂點(diǎn)分配到各個(gè)分區(qū)所產(chǎn)生的增益值Δg。

步驟2選擇產(chǎn)生最大增益的頂點(diǎn)v和其對(duì)應(yīng)的分區(qū)i，將其分配到分區(qū)i，從待分配頂點(diǎn)集合移除v。

步驟3如果待分配頂點(diǎn)集合不為空，更新其他待分配頂點(diǎn)的增益值Δg，返回步驟1，否則，執(zhí)行步驟4。

步驟4輸出分區(qū)結(jié)果。

為提高算法效率，本文對(duì)以上執(zhí)行步驟做了如下兩方面處理：

（1）設(shè)計(jì)一個(gè)二維數(shù)組存儲(chǔ)待分配頂點(diǎn)分配到不同分區(qū)產(chǎn)生的增益值?g，其中二維數(shù)組中的每一行對(duì)應(yīng)一個(gè)待分配頂點(diǎn)，每一列對(duì)應(yīng)一個(gè)分區(qū)。當(dāng)將一個(gè)頂點(diǎn)v分配到分區(qū)i后，其他待分配頂點(diǎn)在各個(gè)分區(qū)增益變化遵循公式（13）：

（2）為方便尋找能夠產(chǎn)生最大增益的頂點(diǎn)，IKGGGP算法采用鄰接表的方式記錄每個(gè)節(jié)點(diǎn)最大增益值產(chǎn)生時(shí)所對(duì)應(yīng)的相關(guān)信息。其中一維數(shù)組的每個(gè)元素對(duì)應(yīng)最大增益范圍內(nèi)的一個(gè)值，并且這些值按降序排列。同時(shí)，每個(gè)元素指向一個(gè)雙向鏈表，用于存儲(chǔ)產(chǎn)生相同最大增益值的頂點(diǎn)信息。本文將最大增益頂點(diǎn)按降序排列可以方便選擇產(chǎn)生最大增益的頂點(diǎn)，采用雙向鏈表是為了方便刪除處理過(guò)的頂點(diǎn)。

4.2 動(dòng)態(tài)圖分割

實(shí)際應(yīng)用中，RDF數(shù)據(jù)是在不斷變化的。對(duì)應(yīng)的圖分割算法也應(yīng)該針對(duì)這些變化給出合理的解決方案，以保證數(shù)據(jù)分割一直滿(mǎn)足邊割和平衡性的要求。本文針對(duì)RDF圖動(dòng)態(tài)變化（元組的插入和刪除兩方面，更新操作可以用刪除和插入實(shí)現(xiàn)）設(shè)計(jì)了RDF圖的動(dòng)態(tài)分割及調(diào)整策略（Dynamic Partitioning and Adjustment Strategy of RDF，DPAS）。

4.2.1 插入元組insert（s，p，o）

新增元組插入到原RDF圖中分三種情況：（1）新增元組的主語(yǔ)和賓語(yǔ)在原始圖中存在；（2）新增元組的主語(yǔ)或賓語(yǔ)只存在一個(gè)；（3）新增元組對(duì)應(yīng)的主語(yǔ)和賓語(yǔ)都不存在。

（1）s和o都存在

當(dāng)s，o在分割圖中已經(jīng)存在時(shí)，插入元組就是在圖中增加一條邊。如果s,o∈Vi，則增加元組不改變目標(biāo)函數(shù)，因此直接插入該元組即可。如果 s∈Vi，o∈Vj，且i≠j，需要判斷以下情況，選擇增益值最大的一種情況添加。

①不移動(dòng)頂點(diǎn)，直接在s和o之間添加一條邊，?g增益值為-1。

②將頂點(diǎn)s或o遷移到對(duì)方所在分區(qū)（頂點(diǎn)遷移的前提是滿(mǎn)足負(fù)載均衡條件）時(shí)，?g的增益值變化如公式（14）：

（2）s或o中有一個(gè)是新頂點(diǎn)

設(shè)已經(jīng)存在的頂點(diǎn)為s，s∈Vi，待加入新節(jié)點(diǎn)為o，則頂點(diǎn)o有兩種分區(qū)選擇。一種是將o加入到分區(qū)i，另一種將o加入到其他某一分區(qū)。產(chǎn)生的增益值如公式（15）。同樣，在保持負(fù)載均衡的前提下選擇具有最大增益值的分區(qū)。

（3）s和o都是新頂點(diǎn)

如果一個(gè)元組的主語(yǔ)和賓語(yǔ)都不存在，說(shuō)明這兩個(gè)頂點(diǎn)和圖中任意一個(gè)頂點(diǎn)都沒(méi)有關(guān)聯(lián)，分配策略是將這兩點(diǎn)分配到具有最少頂點(diǎn)的分區(qū)。

4.2.2 刪除元組delete（s，p，o）

刪除元組就是刪除由頂點(diǎn)s指向o的一條有向邊，如果 |Γ(s)|＞1且 |Γ(o)|＞1，并且 s和 o分別屬于不同的分區(qū)，則刪除邊e可以降低整體邊割又不影響分割平衡性，因此直接刪除邊e即可。

當(dāng)|Γ(s)|=1并且|Γ(o)|=1，或者滿(mǎn)足 s和o的一個(gè)頂點(diǎn)鄰域?yàn)?時(shí)，需要將鄰域?yàn)?的頂點(diǎn)連同邊一起刪除。邊割的降低會(huì)提高圖的分割質(zhì)量，但頂點(diǎn)的刪除有可能導(dǎo)致分割的負(fù)載失衡。又由于插入元組只是局部調(diào)整節(jié)點(diǎn)的分配，因此經(jīng)過(guò)一個(gè)時(shí)間間隔T，圖分割有可能出現(xiàn)局部最優(yōu)的情況。為避免上述情況的發(fā)生，每經(jīng)過(guò)時(shí)間T，將對(duì)圖進(jìn)行一次動(dòng)態(tài)調(diào)整。

（1）平衡性調(diào)整

由于元組的刪除，會(huì)導(dǎo)致分割子圖不均衡。如果存在子圖Gi不滿(mǎn)足負(fù)載均衡的要求，需要對(duì)其進(jìn)行調(diào)整。當(dāng)|Vi|＜「n(1-e)/k?時(shí)，用 Γ(Vi)表示子圖 Gi的鄰域頂點(diǎn)集合。?v∈Γ(Vi)，P(v)=j，當(dāng)將頂點(diǎn)v從分區(qū)j移至分區(qū)i時(shí)，目標(biāo)函數(shù)的增益值為：

從Γ(Vi)中選擇能夠產(chǎn)生最大增益值的頂點(diǎn)v，將其移到分區(qū)Gi中，直到|Vi|滿(mǎn)足公式（3）。

相反，當(dāng)子圖Gi中的頂點(diǎn) |Vi|＞「n(1+e)/k?時(shí)，用η(Vi)表示子圖Gi中與其他子圖有關(guān)聯(lián)的頂點(diǎn)集合。?v∈η(Vi)，?u∈Γ(v)，P(u)=j,j≠i，當(dāng)將 v從分區(qū) i移至分區(qū) j時(shí)，目標(biāo)函數(shù)的增益值為：

同樣從η(Vi)中選擇能夠產(chǎn)生最大增益值?g的頂點(diǎn)v，將其加入到分區(qū)Gj中，直到|Vi|滿(mǎn)足公式（3）。

（2）子圖緊密性

當(dāng)圖分割滿(mǎn)足負(fù)載均衡條件時(shí)，分割子圖內(nèi)部頂點(diǎn)應(yīng)具有緊密的聯(lián)系，而子圖之間頂點(diǎn)聯(lián)系應(yīng)該比較稀疏。本文用子圖的內(nèi)聚度和耦合度來(lái)衡量分割子圖的緊密性。公式（18）和（19）分別給出計(jì)算分割子圖內(nèi)聚度和耦合度的方法。

對(duì)于任意分割子圖，如果它的內(nèi)聚度大于它與其他子圖之間的耦合度，則說(shuō)明子圖內(nèi)部頂點(diǎn)聯(lián)系比較緊密。當(dāng)存在子圖的內(nèi)聚度低于它與其他子圖的耦合度時(shí)，說(shuō)明該子圖內(nèi)部存在一些頂點(diǎn)，這些頂點(diǎn)與其他子圖聯(lián)系更加緊密。

圖3 平衡性調(diào)整整

圖3 （b）是交換（a）中兩個(gè)分割子圖G1和G2中頂點(diǎn)b和e的結(jié)果。對(duì)于分割子圖G1，其在交換節(jié)點(diǎn)前的內(nèi)聚度和耦合度分別是4/10和6/10。當(dāng)交換頂點(diǎn)后，兩個(gè)值分別為5/10和5/10。同理，子圖G2也由5/11和6/11變成5/10和5/10。由此可見(jiàn)，G1和G2的內(nèi)聚度都提升了，而耦合度下降了，最直觀的體現(xiàn)即兩個(gè)子圖之間的邊割降低了。

用η(Vi)表示子圖Gi中與其他子圖相關(guān)聯(lián)的頂點(diǎn)集合。 ?v∈η(Vi)，u∈Γj(v )，j=1,2,…,k且 j≠i，如果 Γ(u)＜Γ(v )，并且u、v在子圖Gi和Gj的鄰域滿(mǎn)足公式（20），就將頂點(diǎn)u和v進(jìn)行交換。

調(diào)整子圖內(nèi)聚度步驟如下：

步驟1根據(jù)公式（18）和（19）計(jì)算分割子圖內(nèi)聚度及子圖間耦合度。

步驟2如果存在子圖cohesion(Gi)＜connection(Gi,Gj)，j=1,2,…,k且 j≠i，執(zhí)行步驟3；否則，跳轉(zhuǎn)到步驟5。

步驟3如果存在v∈η(Vi)，u∈Γj()v 并且 Γ(u)＜Γ()

v ，同時(shí)滿(mǎn)足公式（20），則交換頂點(diǎn)u和v；否則轉(zhuǎn)到步驟5。

步驟4更新子圖內(nèi)聚度及子圖之間耦合度，跳轉(zhuǎn)到步驟2。

步驟5輸出調(diào)整后的分割結(jié)果。

5 實(shí)驗(yàn)

本文實(shí)驗(yàn)選取合成數(shù)據(jù)集（LUBM）和真實(shí)數(shù)據(jù)集（Uniprot）驗(yàn)證RGPDOO算法在分割靜態(tài)和動(dòng)態(tài)RDF圖時(shí)的性能。

5.1 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

LUBM是一種標(biāo)準(zhǔn)化的評(píng)價(jià)語(yǔ)義網(wǎng)算法的合成數(shù)據(jù)集。利用其提供的數(shù)據(jù)生成器可以生成不同規(guī)模大小的RDF數(shù)據(jù)集。Uniprot是一個(gè)可免費(fèi)訪問(wèn)的關(guān)于蛋白質(zhì)序列和功能信息的真實(shí)數(shù)據(jù)集。表1列出了這兩個(gè)數(shù)據(jù)集的一些基本信息。

表1 實(shí)驗(yàn)數(shù)據(jù)表

本文的實(shí)驗(yàn)運(yùn)行硬件環(huán)境為：Inter Xeon 2.00 GHz×24處理器，20 GB內(nèi)存；軟件環(huán)境為：Linux操作系統(tǒng)，C++編程語(yǔ)言。

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

5.2.1 靜態(tài)分割I(lǐng)KGGGP性能驗(yàn)證

本文選擇LUBM50和Uniprot子集（一億條元組）對(duì)靜態(tài)圖分割算法IKGGGP進(jìn)行了驗(yàn)證。實(shí)驗(yàn)中選擇METIS，MLP+METIS和BRGP作為對(duì)比算法，參數(shù)ε=0.3，δ=2m/n。每個(gè)分割算法執(zhí)行三次，取結(jié)果的平均值，平衡性取最大子圖與分割子圖的均值比，四種算法均將數(shù)據(jù)集分割成4、8和16三種不同大小的分區(qū)。圖4給出了四種算法在分割時(shí)間、邊割量和平衡性三方面的對(duì)比結(jié)果。如圖4所示，IKGGGP算法分割時(shí)間優(yōu)于METIS，低于MLP+METIS和BRGP。IKGGGP、MLP+METIS和BRGP的執(zhí)行效率與圖中頂點(diǎn)度數(shù)的分布沒(méi)有直接關(guān)系，因此不受圖中高度頂點(diǎn)的影響。而METIS算法的頂點(diǎn)粗化速度直接受頂點(diǎn)度數(shù)的影響[18]。對(duì)于本文的兩個(gè)數(shù)據(jù)集，數(shù)據(jù)集中存在一些高度頂點(diǎn)，這些頂點(diǎn)的度數(shù)是普通頂點(diǎn)的幾十甚至幾百倍，因此造成METIS算法分割效率低于其他三種算法。其中MLP+METIS和BRGP算法中依靠標(biāo)簽傳播算法（LPA）來(lái)實(shí)現(xiàn)頂點(diǎn)的逐層粗化，每層LPA的時(shí)間復(fù)雜度為O(tm)，其中t為L(zhǎng)PA算法迭代次數(shù)，m對(duì)應(yīng)的是每一層圖中的邊數(shù)。IKGGGP算法需要先計(jì)算頂點(diǎn)與其鄰域之間的相似性找出核心點(diǎn)，然后再進(jìn)行節(jié)點(diǎn)分配，時(shí)間復(fù)雜度為O(m+n)。但I(xiàn)KGGGP算法之所以在效率上仍高于MLP+METIS和BRGP，原因在于IKGGGP算法在對(duì)待分配頂點(diǎn)進(jìn)行分配時(shí)，需要不斷更新待分配頂點(diǎn)的最大增益值。另外，IKGGGP算法的分割效率與待分配頂點(diǎn)的數(shù)目有關(guān)，圖5列出了初始分割時(shí)所產(chǎn)生的三類(lèi)頂點(diǎn)占頂點(diǎn)總數(shù)的比例。從圖5可以看出，內(nèi)核頂點(diǎn)隨著分區(qū)數(shù)目的增加在逐漸降低，但總量仍然超過(guò)30%，因此在對(duì)頂點(diǎn)進(jìn)行分配時(shí)，至少有30%的頂點(diǎn)不參與再分配，這也是IKGGGP算法時(shí)間效率高于METIS的一個(gè)原因。

圖4 IKGGGP初始分割算法性能驗(yàn)證

圖5 初始分割三類(lèi)頂點(diǎn)統(tǒng)計(jì)

在邊割和負(fù)載均衡的結(jié)果中IKGGGP算法要優(yōu)于其他三種算法，其原因在于IKGGGP算法中引入的增益函數(shù)是直接選擇邊割和負(fù)載均衡最優(yōu)的情況進(jìn)行頂點(diǎn)分配，而標(biāo)簽傳播則是間接地實(shí)現(xiàn)邊割和負(fù)載均衡的最優(yōu)，因此IKGGGP算法的邊割和負(fù)載均衡在幾種算法中占有一定優(yōu)勢(shì)。

5.2.2 動(dòng)態(tài)圖分割DPAS性能驗(yàn)證

本部分驗(yàn)證RGPDOO算法動(dòng)態(tài)分割及調(diào)整策略DPAS。DPAS是在已有分割圖的基礎(chǔ)上，根據(jù)RDF圖的動(dòng)態(tài)變化執(zhí)行的。因此，以IKGGGP圖分割結(jié)果為基礎(chǔ)，通過(guò)不斷向圖中插入元組，驗(yàn)證DPAS的性能。本部分選擇Spinner和Fennel兩種動(dòng)態(tài)圖分割算法作為比較算法。實(shí)驗(yàn)中DPAS、Spinner將LUBM50和Uniprot1作為初始靜態(tài)數(shù)據(jù)，其他數(shù)據(jù)都以動(dòng)態(tài)插入方式產(chǎn)生。Fennel以流方式直接增加數(shù)據(jù)，最終插入的數(shù)據(jù)量使LUBM數(shù)據(jù)集達(dá)到LUBM2000，Uniprot數(shù)據(jù)集達(dá)到Uniprot2，DPAS的動(dòng)態(tài)調(diào)整時(shí)間間隔設(shè)為T(mén)=5 s。圖6顯示了三種算法在分割時(shí)間，邊割和平衡性三方面的實(shí)驗(yàn)結(jié)果。其中，F(xiàn)ennel在兩種數(shù)據(jù)集上的分割效率都是最高的，其原因在于Fennel算法采用流式分割，時(shí)間效率是線(xiàn)性的。而Spinner的分割效率要低于Fennel和DPAS，主要是由于Spinner在數(shù)據(jù)變化后，每次都重啟迭代，重新尋找最優(yōu)分割，因此效率會(huì)隨著節(jié)點(diǎn)數(shù)目的增加逐漸降低。RGPDOO算法在靜態(tài)圖數(shù)據(jù)分割中采用的IKGGGP算法效率不高，但動(dòng)態(tài)圖分割部分由于DPAS采用線(xiàn)性的節(jié)點(diǎn)分配方案，頂點(diǎn)的調(diào)整也是基于局部子圖，因此其效率介于Spinner和Fennel之間。

圖6 IRGPA算法性能驗(yàn)證

在邊割和平衡性的實(shí)驗(yàn)結(jié)果中，DPAS的分割效果明顯好于其他兩種算法。雖然Fennel算法也是基于邊割和平衡目標(biāo)函數(shù)進(jìn)行分割的，但DPAS在算法中增加了動(dòng)態(tài)調(diào)整功能，使整體分割不至于陷入局部最優(yōu)。而Spinner基于標(biāo)簽的平衡性是以邊為基準(zhǔn)的，本文比較以節(jié)點(diǎn)為主，因此Spinner平衡性要低于DPAS與Fennel。

圖7 動(dòng)態(tài)調(diào)整對(duì)圖平衡性影響

上述實(shí)驗(yàn)DPAS在運(yùn)行期間都是執(zhí)行元組插入操作，為驗(yàn)證元組刪除及動(dòng)態(tài)調(diào)整有效性，本文每隔時(shí)間T，采用隨機(jī)的方式從分割圖中刪除若干元組。圖7給出了執(zhí)行動(dòng)態(tài)調(diào)整前后圖分割平衡性變化情況。從圖中可以看出，調(diào)整前由于元組的刪除，圖頂點(diǎn)的數(shù)目下降，導(dǎo)致最大子圖失衡程度上升。當(dāng)DPAS增加了動(dòng)態(tài)調(diào)整功能后，圖分割的平衡性會(huì)比調(diào)整前有所降低，使整體圖分割的平衡性始終維持在一個(gè)變化范圍內(nèi)。

5.2.3 RGPDOO在增量圖分割中性能驗(yàn)證

5.2.1 小節(jié)實(shí)驗(yàn)表明IKGGGP算法在初始圖分割時(shí)的效率要低于MLP+METIS和BRGP算法。但其邊割和負(fù)載均衡性都要優(yōu)于其他三種算法。然而隨著數(shù)據(jù)量的不斷增加，將IKGGGP初始分割結(jié)果作為后續(xù)圖分割的基礎(chǔ)，增加的數(shù)據(jù)采用DPAS進(jìn)行動(dòng)態(tài)分割，MLP+METIS、METIS和BRGP面對(duì)增量數(shù)據(jù)采用重新分割的方式進(jìn)行比較，分割效率有了明顯的變化。圖8分別顯示了LUBM和Uniprot兩個(gè)數(shù)據(jù)集在幾種不同分割算法上將數(shù)據(jù)集分割成8個(gè)分區(qū)時(shí)的時(shí)間性能。其中RGPDOO選擇LUBM50數(shù)據(jù)集和Uniprot1的一億條數(shù)據(jù)作為初始靜態(tài)分割的數(shù)據(jù)集。METIS、MLP+METIS和BRGP算法對(duì)應(yīng)不同規(guī)模大小數(shù)據(jù)集的分割時(shí)間都是直接將算法作用于相應(yīng)數(shù)據(jù)集所得到的分割時(shí)間。由圖中曲線(xiàn)可以看出，隨著數(shù)據(jù)集規(guī)模的增加，RGPDOO算法分割時(shí)間增加緩慢，而METIS、MLP+METIS和BRGP算法的分割時(shí)間明顯高于RGPDOO。并且數(shù)據(jù)集越大，越顯示出RGPDOO算法的優(yōu)勢(shì)。其原因在于IRGPA的增量圖分割算法部分在計(jì)算節(jié)點(diǎn)分配時(shí)，只考慮很少一部分與待分配相關(guān)聯(lián)的節(jié)點(diǎn)，因此分割速度很快，而其他的三種算法當(dāng)數(shù)據(jù)規(guī)模變化時(shí)，需要通過(guò)更多的迭代得到最終結(jié)果，增加了算法的運(yùn)行時(shí)間，由此也說(shuō)明RGPDOO在增量數(shù)據(jù)分割時(shí)的有效性。

圖8 IRGPA增量分割效率

6 結(jié)束語(yǔ)

本文從RDF圖分割的兩個(gè)基本目標(biāo)：邊割和平衡性出發(fā)，提出一種基于雙目標(biāo)優(yōu)化的RDF圖分割算法（RGPDOO）。RGPDOO將邊割和分割平衡兩項(xiàng)圖分割指標(biāo)融合到一個(gè)目標(biāo)函數(shù)，并依據(jù)此目標(biāo)函數(shù)，實(shí)現(xiàn)了RDF圖的靜態(tài)和動(dòng)態(tài)分割。其中靜態(tài)圖分割改進(jìn)了KGGGP算法，不僅通過(guò)節(jié)點(diǎn)初始分區(qū)降低了候選節(jié)點(diǎn)集規(guī)模，而且通過(guò)選擇雙目標(biāo)函數(shù)增益值實(shí)現(xiàn)了候選節(jié)點(diǎn)的分配。對(duì)于動(dòng)態(tài)分割部分，本文依據(jù)目標(biāo)函數(shù)給出了元組插入和刪除時(shí)節(jié)點(diǎn)的分配策略（DPAS）。同時(shí)，為了避免局部最優(yōu)或分割失衡，DPAS每隔時(shí)間T，都會(huì)依據(jù)分割平衡性和子圖內(nèi)聚度對(duì)子圖進(jìn)行動(dòng)態(tài)調(diào)整，以保證圖分割始終滿(mǎn)足最小化邊割和分割平衡兩項(xiàng)目標(biāo)。實(shí)驗(yàn)選擇了兩種常用的數(shù)據(jù)集進(jìn)行測(cè)試，分別從分割效率、邊割和平衡性三方面驗(yàn)證了靜態(tài)和動(dòng)態(tài)圖分割算法的性能。結(jié)果表明RGPDOO能夠?qū)崿F(xiàn)RDF圖的有效分割。但同其他分割算法相比，RGPDOO的分割效率略低于其中一些算法，這也是今后研究的方向。

[1]RDF[EB/OL].http：//www.w3.org/TR/rdf-concepts/.

[2]Yu L.Linked open data.A developer’s guide to the semantic web[M].Berlin Heidelberg：Springer，2011：409-466.

[3]Lee K，Liu L，Tang Y，et al.Efficient and customizable data partitioning framework for distributed big RDF data processing in thecloud[C]//IEEE Sixth International Conference on Cloud Computing，2013：327-334.

[4]Lee K.Efficient data partitioning model for heterogeneous graphs in the cloud[C]//High Performance Computing，Networking，Storage and Analysis，2013：1-12.

[5]Wu B，Zhou Y，Yuan P，et al.Scalable SPARQL querying using path partitioning[C]//International Conference on Data Engineering.IEEE，2015：795-806.

[6]Huang J，Abadi D J，Ren K.Scalable sparql querying of large rdf graphs[J].Proceedings of the VLDB Endowment，2011，4（11）：1123-1134.

[7]Wang L，Xiao Y，Shao B，et al.How to partition a billionnode graph[C]//2014 IEEE 30th International Conference on Data Engineering（ICDE），2014：568-579.

[8]朱牧，孟凡榮，周勇.基于鏈接密度聚類(lèi)的重疊社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)研究與發(fā)展，2013，50（12）：2520-2530.

[9]Tsourakakis C，Gkantsidis C，Radunovic B，et al.FENNEL：streaming graph partitioning for massive scale graphs[C]//ACM International Conference on Web Search and Data Mining，2014：333-342.

[10]張曉媛，張珩，翟健.基于鄰域的大規(guī)模圖數(shù)據(jù)動(dòng)態(tài)分割算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2016，25（9）：193-199.

[11]Martella C，Logothetis D，Loukas A，et al.Spinner：scalable graph partitioning in the cloud[J].Computer Science，2015.

[12]Pujol J M，Erramilli V，Siganos G，et al.The little engine（s） that could：scaling online social networks[J].IEEE/ACM Transactions on Networking，2012，20（4）：1162-1175.

[13]Yang S，Yan X，Zong B，et al.Towards effective partition management for large graphs[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data，2012：517-528.

[14]Xu N，Chen L，Cui B.LogGP：a log-based dynamic graph partitioning method[J].Proceedings of the VLDB Endowment，2014，7（14）：1917-1928.

[15]Predari M，Esnard A.A k-way greedy graph partitioning with initial fixed vertices for parallel applications[C]//Euromicro International Conference on Parallel，Distributed，and Network-Based Processing，2016：280-287.

[16]Zhou Y，Cheng H，Yu J X.Graph clustering based on structural/attribute similarities[J].Proceedings of the VLDB Endowment，2009，2（1）：718-729.

[17]Khosravi-Farsani H，Nematbakhsh M，Lausen G.SRank：Shortest paths as distance between nodes of a graph with application to RDF clustering[J].Journal of Information Science，2013，39（2）：198-210.

[18]Yao L，Wang Z，Li Z，et al.A novel coarsening scheme for multilevel graph partitioning[C]//International Conference on Biomedical Engineering and Informatics，2011：2091-2094.

CHEN Zhikui1,LENG Yonglin1，2

1.School of Software Technology,Dalian University of Technology,Dalian,Liaoning 116620,China 2.College of Information Science and Technology,Bohai University,Jinzhou,Liaoning 121000,China

RDF graph partitioning algorithm based on double objective optimization.Computer Engineering and Applications,2017,53（21）：24-31.

Distributed storage is a more effective method for the mass data storage.And,the data partitioning is the premise of distributed storage.In facing of the growing semantic web data,RDF Graph Partitioning algorithm is proposed by Double Objective Optimization（RGPDOO）.RGPDOO fuses edge cut and load balancing together to get an objective function.According to this objective function,RGPDOO achieves static and dynamic partitioning of RDF graph.For the static partitioning,an initial partitionis executed to divide the node into three kinds：kernel nodes,boundary nodes and freedom nodes.And then,the boundary and freedom nodes are distributed to apartition with the max gain of objective function.For the dynamic partitioning,the insertion and deletion solution of triples are given by the objective function.And,RGPDOO will execute a dynamic adjustment at a certain time interval according to the balance and tightness of partitioning subgraph to satisfy the partitioning object.Finally,the algorithm is tested on synthetic and real datasets in comparison with several general graph partitioning algorithms.The experimental results show that RGPDOO is more suitable for RDF graph partitioning.

RDF graph;static partitioning;dynamic partitioning;edge cut;load balancing

A

TP311

10.3778/j.issn.1002-8331.1706-0426

國(guó)家自然科學(xué)基金（No.U1301253，No.61672123）；廣東省科技計(jì)劃（No.2015B010110006）；國(guó)家重點(diǎn)研發(fā)計(jì)劃（No.2016YFD0800300）；遼寧省博士科研啟動(dòng)基金項(xiàng)目（No.201601348，No.201601349）。

陳志奎（1968—），男，博士，教授，研究領(lǐng)域?yàn)槲锫?lián)網(wǎng)理論與應(yīng)用、云計(jì)算與大數(shù)據(jù)處理，E-mail：zkchen@dlut.edu.cn；冷泳林（1978—），女，博士研究生，副教授，研究領(lǐng)域?yàn)閿?shù)據(jù)存儲(chǔ)與索引，不完整數(shù)據(jù)填充。

2017-06-30

2017-09-25

1002-8331（2017）21-0024-08