[發明專利]一種海量知識圖譜分布式管理與查詢方法

有效

• 申請號: 202110024902.9
• 申請日: 2021-01-08
• 公開（公告）號: CN112732933B
• 公開（公告）日: 2022-09-06
• 發明（設計）人: 李彭偉;李亞釗;程浚;張慶海;劉博;李子;吳詩婳;闞凌志;郭婉;陳娜
• 申請（專利權）人: 中國電子科技集團公司第二十八研究所
• 主分類號: G06F16/36
• 分類號: G06F16/36;G06F16/35;G06F16/33;G06F16/31
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 胡建華

本發明公開了一種海量知識圖譜分布式管理與查詢方法，包括1、將知識圖譜中的節點作為網格進行管理，BFS搜索，得到相鄰網格，計算網格密度；2、遍歷所有節點，當節點密度大于密度閾值時，建立新集群，并將該節點加入，再從該節點BFS搜索，若發現臨近有其他高密度節點，將其加入同一集群；3、基于星形擴張的查詢，將圖譜中某個節點設為初始節點，把這個節點和與其直接相連的其它節點連接起來，一次遍歷進行一次星形查詢。依次以一跳查詢的節點為中心，再次開展星形查詢即依次星形擴張，重復該過程，直至達到指定跳數或遍歷完所有節點。本發明提供的方法實現了知識圖譜的按需分割，顯著提高查詢的性能，同時實現了跨不同分割子圖的關聯查詢。

技術領域

本發明涉及知識圖譜與數據管理數據挖掘領域，具體涉及一種海量知識圖譜分布式管理與查詢方法。

背景技術

近年來，隨著各類數據處理的需求日益增加，數據的規模也越來越大，人們面臨著處理各種大容量，多樣化和高增長率數據的嚴峻挑戰。據估計，目前大型搜索引擎的索引量已經超過了一萬億鏈接，預計在一年內超過十萬億；2017年，Facebook擁有超過20億活躍用戶，擁有數以千億的好友關系鏈接；百度知識圖譜在上線五年的時間里，規模增長了160倍；當前公開的知識圖譜數據量早已達到了千億級別；據中國互聯網絡信息中心CNNIC(ChinaInternet Network Information Center)統計，2010年中國網頁規模就達到了600億，年增長率78.6％。而且不只是互聯網中的圖規模龐大，隨著生物化學等領域科學數據采集手段的豐富，人腦級別的圖建模已經達到了百萬億的規模。如何處理這些規模巨大結構復雜的大圖變成了一大難題。知識圖譜就是這些圖中的一種。

發明內容

發明目的：本發明所要解決的技術問題是針對現有技術的不足，提供一種海量知識圖譜分布式管理與查詢方法。

為了解決上述技術問題，本發明公開了一種海量知識圖譜分布式管理與查詢方法，包括如下步驟：

步驟1，基于密度的節點聚類，將知識圖譜中的節點作為網格進行管理，并對網格之間沒有空間結構時無法通過下標直接訪問的問題，通過廣度優先搜索BFS(BreadthFirst Search)，將搜索的單位層數設為1，通過搜索得到與某個網格相鄰的其它網格，計算網格的密度，即節點的密度；

步驟2，基于標記的知識圖譜分割，在得到知識圖譜中所有節點的密度信息后，遍歷這些節點，遇到節點密度大于密度閾值tv時，就建立一個新的集群，并將該節點加入，該節點標記為高密度節點；然后再從這個節點開始進行廣度優先搜索，在此過程中，如果發現臨近有其他高密度節點，也將其加入同一個集群；

步驟3，基于星形擴張的查詢，所述星形擴張指的是，將知識圖譜中某個節點設置為初始節點，并把這個節點和與其直接相連的其它節點連接起來，類似一個擴張的星座圖，一次遍歷，即一跳查詢，稱為一個星形查詢；依次以一跳查詢的節點為中心，再次開展星形查詢，即兩跳查詢，稱為一次星形擴張，重復該過程，直至達到指定跳數或遍歷完所有節點。

在一種實現方式中，所述步驟1中所述網格的密度通過計算該網格與其相鄰網格的出度與入度之和獲得。

在一種實現方式中，所述步驟2包括：

步驟2-1，依次遍歷讀取并解析知識圖譜三元組；

步驟2-2，遍歷知識圖譜中的所有節點，如果節點的密度大于或等于密度閾值tv，該節點標記為高密度節點，執行步驟2-3；如果全部遍歷結束，執行步驟2-4；否則繼續執行步驟2-2；

步驟2-3，建立一個空的集群，將高密度節點加入集群中，然后以這個高密度節點為中心開始廣度優先搜索，若搜索到其他高密度節點，則將其加入這個集群，并結束當前節點的搜索過程；以搜索到的其他高密度節點為中心進行廣度優先搜索，迭代上述過程，直至搜索不到高密度節點為止；搜索結束后，繼續執行步驟2-2；