[發明專利]一種面向知識圖譜的大規模數據增量處理方法

在審

• 申請號: 202010189883.0
• 申請日: 2020-03-18
• 公開（公告）號: CN111382320A
• 公開（公告）日: 2020-07-07
• 發明（設計）人: 劉穎;朱連宏;關禮安;白新有;張巍;張洋銘;陳劍;羅承昆
• 申請（專利權）人: 軍事科學院系統工程研究院系統總體研究所
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 中國航天科工集團公司專利中心 11024
• 代理人: 張國虹

本發明公開了一種面向知識圖譜的大規模數據增量處理方法，包括步驟：(10)利用現有的圖分割算法將初始的圖分割成多個子圖；(20)獲取時間片周期中的圖的增量序列；(30)按照各個子圖負載均衡的原則把圖的增量序列映射成點和邊的插入、刪除操作，以及邊的權值更新操作；(40)計算子圖相互之間的緊密度矩陣；(50)如果子圖之間的緊密度大于子圖內部的緊密度，則動態調整節點與子圖的隸屬關系，直至子圖相互之間滿足內部高內聚，外部低耦合的要求。本發明只將增量的節點或邊動態的分配到對應的子圖中，從而降低了計算開銷和時間代價；通過調整部分節點實現對子圖的動態調整，避免了對整個子圖進行重新分割，降低了動態維護開銷。

技術領域

本發明屬于圖數據庫技術領域，特別是針對大規模動態圖數據，提出了一種面向知識圖譜的大規模數據增量處理方法。

背景技術

圖是計算機科學中常用的一類抽象數據結構，圖的普適性使得現實世界的實際網絡往往能夠抽象成圖數據模型表示，其在基于計算機數據庫的數據處理技術領域具有廣泛的應用前景。目前己經被廣泛地應用于諸如計算機科學、語言學、邏輯學、物理、化學、電信工程等領域。然而，隨著網絡和計算機技術的飛速發展，實際網絡規模的快速增長，導致圖的規模日益增大；同時也加劇了現實網絡的動態演化程度，導致圖隨時間不斷變化。因此如何對大規模動態圖進行高效地處理成為了近年來的研究熱點和難點。

在現今的信息時代，信息量以爆炸式的模式增長也導致了圖數據的規模越來越大，很難通過單機完成對大規模圖的分析和計算等處理需求。因此，利用高效的圖分割方法將大規模圖數據進行分割，是提高大規模圖數據分析和計算的有效手段。圖分割的基本思想是將一個大規模的圖分割成為多個子圖，子圖中的對象間具有強關聯性，而不同子圖之間的對象則需要是弱相關的，也就是說子圖內部節點之間的聯系具有緊密特性，而子圖之間的節點的關聯程度應該具有稀疏性。

日益廉價的計算機硬件和廣泛應用的分布式計算集群系統的出現使得借助于分布式技術將圖進行有效的分割，將圖數據進行合理的分布，有效地減少分布式計算中的通信開銷，從而實現對大規模圖分而治之的處理。

通過對圖分割技術的深入研究發現，目前己有的一些方法雖然可以有效地應用于大規模圖的分割，然而現階段對于圖分割技術的研究主要都是針對靜態圖分割的研究，即它們認為圖是靜態的，不隨時間而變化的。然而，在現實生活中，用圖數據表示的諸多領域中，如社交網絡，生物信息網等，大多都是隨時間動態演化的且規模也隨之增大。大規模圖的動態性表現為節點或邊的插入、節點間邊權值的變化、節點或邊的刪除。當前大規模圖或網絡大多隨時間而動態變化，現有的圖分割方法主要面向靜態圖數據，無法滿足現實的需求，因此解決這種大規模動態圖的分割問題成為了本發明的研究重點。

發明內容

本發明的目的在于提供一種面向知識圖譜的大規模數據增量處理方法，屬于圖數據庫技術領域，能夠降低對動態圖數據進行分割的計算開銷和時間代價；同時當圖發生變化的時候，還能避免對整個子圖進行重新分割，降低了動態維護開銷。

實現本發明目的的技術解決方案如下：

本發明提出一種面向知識圖譜的大規模數據增量處理方法，包括如下步驟：(10)利用現有的圖分割算法將初始的圖分割成多個子圖；(20)獲取時間片周期中的圖的增量序列；(30)按照各個子圖負載均衡的原則把圖的增量序列映射成點和邊的插入、刪除操作，以及邊的權值更新操作；(40)計算子圖相互之間的緊密度矩陣；(50)如果子圖之間的緊密度大于子圖內部的緊密度，則動態調整節點與子圖的隸屬關系，直至子圖相互之間滿足內部高內聚，外部低耦合的要求。