[發明專利]一種基于BFS森林的社交網絡中的知識圖譜數據布局方法

有效

• 申請號: 201811082264.0
• 申請日: 2018-09-17
• 公開（公告）號: CN109271478B
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 施展;馮丹;曹孟媛;戴凱航;王子毅;劉上;楊蕾;楊文鑫;陳碩;陳靜
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/36;G06F16/33
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智;曹葆青

本發明公開了一種基于BFS森林的社交網絡中的知識圖譜數據布局方法，包括：對社交網絡中的知識圖譜進行一次全圖的全局BFS遍歷，得到全局BFS序列；將當前限長BFS子樹的起始點初始化為全局BFS序列的起始序號；從起始點出發，使用限長BFS遍歷社交網絡中的知識圖譜，直至圖中所有節點都被遍歷，最終得到BFS森林序列；利用所述BFS森林序列對社交網絡中的知識圖譜的節點進行更新，知識圖譜數據布局結束。本發明使用BFS森林去遍歷全圖，限長BFS子樹的局部性已經符合限長圖遍歷算法需求；以全局BFS序列作為“BFS森林”起始點選擇依據，使BFS子樹起始點的選擇更加符合限長圖遍歷的需求，使多個BFS子樹組成的序列滿足整體順序性，提高了算法執行效率。

技術領域

本發明屬于知識圖譜推理領域，更具體地，涉及一種基于BFS森林的社交網絡中的知識圖譜數據布局方法。

背景技術

基于路徑的知識推理方法的特征提取階段PCWR是其效率瓶頸，傳統的在內存模式下對特征提取階段的優化難以滿足社交網絡知識圖譜的數據量逐漸增大。現有技術提出使用限長圖遍歷算法代替PCWR進行特征提取，其整個過程為：數據布局策略對知識圖譜數據進行處理，獲得預處理后的知識圖譜數據。然后再利用外存模式圖處理系統對預處理后的知識圖譜數據進行分區。最后基于路徑的知識推理在外存模式圖處理系統上執行限長圖遍歷算法，對分區后的知識圖譜進行特征提取、推理和預測。針對限長圖遍歷算法的數據布局策略是一種通過對知識圖譜節點進行偏序排列，并依此進行序號重排，在不影響具有選擇調度機制的外存模式圖處理系統的任何模塊設計的情況下，通過提高外存模式圖處理系統數據分區的順序性與局部性，進而減少算法執行過程中的分區數據讀取次數，來提高外存模式下基于路徑的知識推理算法中“特征提取”階段效率的預處理手段。

現有的外存模式下基于路徑的知識推理的數據布局策略包括：GraphChi頂點排序數據布局策略、X-Stream頂點非排序數據布局策略、GridGraph二維頂點數據布局策略。經分析后發現，它們都是基于圖數據布局，以節點序號進行分塊，并以此為基礎設計了各具特色的計算模型。其中，GraphChi以及GridGraph均保證了每次讀取分區數據塊時僅有非常少量隨機I/O讀寫，大大提高了圖算法執行效率，卻沒有利用限長圖遍歷算法的局部性去減少算法執行過程中的分區數據塊讀寫次數，還有針對限長圖遍歷算法的執行效率優化空間。而X-Stream由于缺乏選擇調度機制，無法受益于此。

綜上所示，現有的外存模式下基于路徑的知識推理的數據布局策略中的數據分區局部性和順序性均有所欠缺，限長圖遍歷算法的執行效率低。

發明內容

針對現有技術的缺陷，本發明的目的在于解決現有技術中外存模式下基于路徑的知識推理的數據布局策略中的數據分區局部性和順序性均有所欠缺，限長圖遍歷算法的執行效率低的技術問題。

為實現上述目的，第一方面，本發明實施例提供了一種基于BFS森林的社交網絡中的知識圖譜數據布局方法，所述BFS森林由多個限長BFS子樹組合，該方法具體包括以下步驟：

S1.對社交網絡中的知識圖譜進行一次全圖的全局BFS遍歷，得到全局BFS序列；

S2.將當前限長BFS子樹的起始點初始化為全局BFS序列的起始序號；

S3.從當前限長BFS子樹的起始點出發，使用限長BFS遍歷社交網絡中的知識圖譜，直至圖中所有節點都被遍歷，最終得到BFS森林序列；

S4.利用所述BFS森林序列對社交網絡中的知識圖譜的節點進行更新，社交網絡中的知識圖譜數據布局結束。

具體地，步驟S3具體如下：

S31.從當前限長BFS子樹的起始點出發，限長BFS以限制步長n遍歷社交網絡中的知識圖譜，得到一個限長BFS序列，并記錄當前BFS子樹最后一個節點的序號；