[發明專利]一種大圖計算中數據訪問方法及系統

有效

• 申請號: 201810725214.3
• 申請日: 2018-07-04
• 公開（公告）號: CN110688055B
• 公開（公告）日: 2020-09-04
• 發明（設計）人: 張廣艷;鄭緯民
• 申請（專利權）人: 清華大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

本發明提供的一種大圖計算中數據訪問方法及系統，通過將目標圖數據文件進行預處理，獲得目標圖數據文件對應的緊湊圖數據文件，通過索引位圖記錄目標圖數據文件在各迭代步驟中的活躍頂點，根據活躍頂點確定各迭代步驟中的有用邊數據和無用邊數據，根據有用邊數據和無用邊數據確定各迭代步驟對應的所有有用邊數據塊，并根據有用邊數據塊的起始位置和大小生成I/O請求，從而在處理I/O請求時可直接根據起始位置和大小從緊湊圖數據文件中訪問對應的有用邊數據塊中的各個邊數據。該方法及系統綜合考量了外存儲設備尋址開銷和外存儲設備I/O開銷，一定程度上減少了無用邊數據的外存儲設備I/O，并確保了邊數據訪問的順序性，有效提高了大圖計算的整體性能。

技術領域

本發明涉及圖計算技術領域，更具體地，涉及一種大圖計算中數據訪問方法及系統。

背景技術

隨著社交網絡、生物信息網絡和信息技術的高速發展，使得以這些信息為對象的圖數據日益增大。基于外存儲設備的大圖計算系統，在處理大規模數據的計算問題時，由于計算機內存容量有限，所以往往通過使用相對廉價的外存儲設備來擴展大圖計算的問題規模。這樣，對于這類基于外存儲設備的大圖計算系統來說，外存儲設備I/O往往是其性能瓶頸。另外，圖算法是具有迭代性質的算法，并且在每次迭代當中，并不是所有的邊數據都必須被使用到的，因此如何有效得減少這些無用邊數據的外存儲設備I/O，并且把額外的開銷降低是一個技術挑戰。

目前，解決上述問題的有兩類方法。第一類是靜態分區的選擇性調度策略，這類方法的主要思想是，在圖數據預處理階段把所有數據按照某個分區方法進行靜態的分區，然后在計算時跳過這些沒有任何有用邊數據的分區，該方法雖然可以在一定程度上減少外存儲設備I/O的數量，但是當分區內只有少數幾條有用邊時，該方法仍然需要讀取整個分區，因此不能充分減少無用邊數據。另一類方法是圖數據重劃分，這類方法的主要思想是，在一次迭代計算結束后，將原始的圖數據，進行重新劃分，在這一過程中，在接下來的計算中不會被用到的圖數據將會被剔除，不會出現在新的劃分中，這樣可以極大地減少都無用數據的外存儲設備I/O和相關的計算，但是這類方法在每一次重劃分的過程中都會引入額外的外存儲設備I/O開銷。

發明內容

本發明為了克服現有技術中圖計算過程中外存儲設備I/O開銷過大，導致圖計算的整體性能較低的問題，提供一種大圖計算中數據訪問方法及系統。

一方面，本發明提供一種大圖計算中數據訪問方法，包括：

計算目標圖數據文件中每個頂點的出度信息，根據所有頂點的出度信息將所有頂點有序劃分成多個頂點集合，對于任意一個頂點集合，將該頂點集合中所有頂點對應的邊數據寫入對應的分區文件中，將所述分區文件中不同頂點對應的邊數據進行排序，將排序后的分區文件寫入緊湊圖數據文件；

調用所述目標圖數據文件對應的迭代算法在當前迭代步驟對應的索引位圖，根據所述索引位圖依次獲取當前迭代步驟對應的所有有用邊數據塊，每個所述有用邊數據塊包括多個邊數據；

對于任意一個有用邊數據塊，將該有用邊數據塊中第一個邊數據在所述緊湊圖數據文件中的位置作為該有用邊數據塊的起始位置，并根據該有用邊數據塊中所有邊數據的數量確定該有用邊數據塊的目標大小，根據所述起始位置和所述目標大小生成I/O請求，將所述I/O請求加入I/O請求隊列中；

從所述I/O請求隊列中依次取出所述I/O請求，并根據所述I/O請求中的起始位置和目標大小訪問所述緊湊圖數據文件中的邊數據。

優選地，所述將該頂點集合中所有頂點對應的邊數據寫入對應的分區文件中，之前還包括：

對于任意一個頂點集合，獲取該頂點集合中的所有頂點；

對于任意一個頂點，將該頂點作為源頂點，獲取與所述源頂點對應的目標頂點，將該頂點與所有所述目標頂點的組合作為該頂點對應的邊數據。

優選地，所述將所述分區文件中不同頂點對應的邊數據進行排序，具體為：