[發明專利]一種單機核外屬性圖計算方法

在審

• 申請號: 202110334310.7
• 申請日: 2021-03-29
• 公開（公告）號: CN113065035A
• 公開（公告）日: 2021-07-02
• 發明（設計）人: 鐘鳴;鄭盈儀;荊澤華
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/906
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 許蓮英

本發明公開了一種單機核外屬性圖計算方法。本發明構建屬性圖；將屬性圖的頂點集以外層不對稱網格分圖策略算法分簇；對得到的每個邊集合以內層不對稱網格分圖策略算法細化分簇；按序重組得到的細粒度邊集合；重組得到的邊集合；構建拓撲數組和邊的屬性的數組；構建頂點的屬性數組；根據用戶給定的屬性條件限制標記滿足限制的拓撲子圖；根據用戶給定的計算任務流式遍歷拓撲圖。本發明優化了圖算法對底層存儲系統的利用，保留了單機核外圖計算系統的優勢，且無需對同一屬性圖的不同圖計算任務重新分圖。

技術領域

本發明屬于計算機科學技術領域，尤其涉及一種單機核外屬性圖計算方法。

背景技術

隨著現實生活中圖數據(如：社交網絡、用戶-物品網絡、路網、交易網絡等等)的快速增長，用戶需要從這些圖數據中挖掘具有潛在價值的信息的高效計算系統。由于現實場景下的圖往往包含上十億級的頂點和邊，近年來，大規模圖計算已成為研究領域中的熱點問題。

大規模圖計算系統主要可分為兩類，即分布式系統和單機系統。分布式系統通常是處理大規模數據的自然的選擇，目前已有許多分布式圖計算系統的相關研究。由于分布式系統需要將圖分布在集群的若干臺機器上，故分布式系統需要把大規模圖切分為若干子圖，即“分圖”(partitioning)，并將這些子圖分別分布到不同機器上。圖的分散分布使得分布式系統執行圖算法任務時不可避免地在機器間進行大量消息交換與合并。雪上加霜的是，現實世界中許多圖的偏斜度分布(skewed degree distribution)、高密度(highdensity)和大直徑(large diameter)等特征導致分布式系統產生諸如負載不平衡(loadimbalance)，同步開銷(synchronization overhead)和容錯開銷(fault toleranceoverhead)等問題。單機系統則能夠有效避免機器間通信帶來的問題。單機圖計算系統又可細分為單機核內(in-memory)圖計算系統和單機核外(out-of-core)圖計算系統。單機核內圖計算系統將圖數據完全存放在內存中，其能夠處理的圖數據規模受內存大小的限制，而單機核外圖計算系統則同時利用了機器的內存與外存存儲和處理圖數據，因此具有更佳的可擴展性。同時，相較于分布式系統，單機核外圖計算系統僅允許內存和本地外存之間進行數據交換，從而大大降低了通信開銷。

由于單機核外圖計算系統涉及內外存之間的數據交換，引入分圖策略能夠更加有效組織數據，提升系統性能，因此現有單機核外圖計算系統研究將分圖策略作為主要問題之一考慮。“對稱網格”分圖策略是現有主流技術方案之一，其將頂點ID劃分為若干個區間，根據邊的源頂點ID所在區間確定該邊所在網格的“行”，根據邊的目的頂點ID所在區間確定該邊所在網格的“列”，在計算過程中通過以“行”或“列”為導向的網格加載方式控制需要加載的頂點數據，被加載的網格會同時加載其所在“行”對應的頂點區間的所有頂點的相關變量和所在“列”對應的頂點區間的所有頂點的相關變量，其中“行”頂點數據涉及外存的“讀”，而“列”頂點數據涉及外存的“寫”。但是，計算機外存讀寫速度不一致的硬件特性使得“對稱網格”分區策略中的“行”和“列”數據加載速度不一致，“行”讀數據遠快于“列”寫數據，導致計算資源和時間的浪費。因此，如何設計分圖策略使得單機核外圖計算系統的性能盡可能提升是單機核外圖計算系統研究與應用中的關鍵問題之一。

此外，在現有的單機核外圖計算系統的研究中，盡管許多現實場景中的圖都具有大量的屬性數據，但這些單機核外圖計算系統都未考慮具有屬性的圖的圖計算問題。例如，針對網絡圖(web graph)，用戶需要計算生成時間在指定范圍內的網頁排名(PageRank)，以便用戶了解這段時間內的熱門網頁。但現有的僅考慮拓撲圖計算的單機核外系統無法執行此類任務。一種簡單的解決方案是利用數據庫查詢引擎來選擇滿足時間條件的邊和頂點，即從原始圖數據中提取符合條件的子圖，然后再導入到單機核外圖計算系統處理該子圖。但是，該解決方案的一個主要問題是，提取的子圖由于拓撲結構的變化需要在外存上重新分圖，這意味著單機核外圖計算系統需要針對每個特定條件限制的屬性圖計算任務進行分圖處理，這對時間和計算資源來說都是極大的浪費。因此，如何高效地計算屬性圖是單機核外屬性圖計算系統研究與應用中的關鍵問題。

發明內容