[發(fā)明專利]一種基于多層劃分框架的RDF分布式存儲(chǔ)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810803364.1
• 申請(qǐng)日: 2018-07-20
• 公開（公告）號(hào): CN109344259B
• 公開（公告）日: 2022-02-22
• 發(fā)明（設(shè)計(jì)）人: 劉均;王瑞杰;晉毓?jié)?/a>;張鐸;魏筆凡;王萌;姚思雨;曾宏偉
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F16/36
• 分類號(hào): G06F16/36;G06F16/35
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 徐文權(quán)

1.一種基于多層劃分框架的RDF分布式存儲(chǔ)方法，其特征在于，該方法通過MMA算法和MSLM算法實(shí)現(xiàn)對(duì)RDF圖的粗糙化，通過B_AP算法實(shí)現(xiàn)對(duì)RDF圖的k-way分割，具體步驟如下：

Step1執(zhí)行以下初始化操作：

101)RDF圖的初始化：設(shè)RDF三元組的主語集合為T_s，謂語集合為T_p，賓語集合為T_o，那么定義RDF圖為：G＝(V,E)，其中V＝{v|v∈T_s∪T_o}，并且假設(shè)n＝|V|表示RDF圖中頂點(diǎn)的個(gè)數(shù)，m＝|E|表示RDF圖邊的數(shù)量；

102)數(shù)據(jù)預(yù)處理：將RDF數(shù)據(jù)的N-Triple型數(shù)據(jù)集全部處理為圖格式，為后續(xù)在RDF圖上的算法運(yùn)行做準(zhǔn)備；

Step2通過MMA算法首先對(duì)RDF圖的頂點(diǎn)移動(dòng)進(jìn)行優(yōu)化：在MMA算法中設(shè)定ε∈[β,0.5)，其中0＜β＜0.5，當(dāng)模塊度的增值大于ε，進(jìn)行移動(dòng)頂點(diǎn)；

Step3通過MSLM算法對(duì)RDF圖進(jìn)行粗糙化：基于模塊度的MSLM算法將RDF圖的規(guī)模進(jìn)行壓縮，達(dá)到粗糙化RDF圖的目的，其具體的優(yōu)化步驟如下：

301)RDF圖中存在大量的屬性節(jié)點(diǎn)，其入度都為1，將RDF圖中所有的入度為1的頂點(diǎn)都等同于屬性節(jié)點(diǎn)，即在算法運(yùn)算過程，如果節(jié)點(diǎn)的入度為1，直接跳過進(jìn)行下一個(gè)頂點(diǎn)的運(yùn)算；

302)RDF圖中存在著大量小社團(tuán)，但是在模塊度增加的情況下不斷被吞并，所以設(shè)置浮動(dòng)參數(shù)來調(diào)節(jié)保護(hù)小社團(tuán)的存在；

Step4通過B_AP算法對(duì)RDF圖進(jìn)行k-way分割，實(shí)現(xiàn)分割的平衡性和最小邊割的目標(biāo)。

2.根據(jù)權(quán)利要求1所述的基于多層劃分框架的RDF分布式存儲(chǔ)方法，其特征在于，Step2中所述的MMA算法描述如下：

假設(shè)頂點(diǎn)v從c₁移動(dòng)到了c₂，則對(duì)于c₁和c₂的模塊度的變化如下：

式中E(c₁)和E(c₂)表示粗糙子圖c₁和c₂中的邊數(shù)，而和表示粗糙子圖中c₁和c₂頂點(diǎn)v的鄰居頂點(diǎn)；所以，模塊度增值ΔQ的計(jì)算公式如下：

ΔQ＝ΔQ₁+ΔQ₂ (7)。

3.根據(jù)權(quán)利要求2所述的基于多層劃分框架的RDF分布式存儲(chǔ)方法，其特征在于，Step3中所述的MSLM算法描述如下：

對(duì)于RDF圖運(yùn)行MSLM算法后，計(jì)算模塊度值變量ΔQ'，假設(shè)計(jì)算社團(tuán)c₁的某個(gè)頂點(diǎn)v_i進(jìn)行移動(dòng)，其模塊度變化計(jì)算公式如下：

式中，ω_in(v_i)表示由頂點(diǎn)v_i入射社團(tuán)c₁的權(quán)重之和，∑_tot表示入射社團(tuán)c₁的總權(quán)重，而ω(v_i)表示頂點(diǎn)v_i的總權(quán)重。