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

有效

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

1.一種大圖計算中數據訪問方法，其特征在于，包括：

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，所述將該頂點集合中所有頂點對應的邊數據寫入對應的分區文件中，之前還包括：

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

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

3.根據權利要求1所述的方法，其特征在于，所述將所述分區文件中不同頂點對應的邊數據進行排序，具體為：

根據所述分區文件中所有頂點的ID信息和出度信息初始化每個頂點對應的偏移量；

對于任意一個頂點，根據該頂點對應的偏移量確定該頂點對應的目標位置，將該頂點對應的邊數據存儲在所述目標位置。

4.根據權利要求1所述的方法，其特征在于，所述調用所述目標圖數據文件對應的迭代算法在當前迭代步驟對應的索引位圖，之前還包括：

根據所述目標圖數據文件對應的迭代算法在上一次迭代步驟中的迭代運算構建當前迭代步驟對應的索引位圖。

5.根據權利要求4所述的方法，其特征在于，所述根據所述目標圖數據文件對應的迭代算法在上一次迭代步驟中的迭代運算構建當前迭代步驟對應的索引位圖，具體為：

對于所述目標圖數據文件中的任意一個頂點，根據該頂點在上一次迭代步驟中的迭代運算判斷該頂點在當前迭代步驟中是否為活躍頂點；若該頂點在當前迭代步驟中為活躍頂點，則將該頂點對應的位圖位設置為第一數值，若該頂點在當前迭代步驟中為非活躍頂點，則將該頂點對應的位圖位設置為第二數值；

根據所有頂點的ID信息將所有頂點的位圖位順序排列，并給預設數量的位圖位設置一個對應的索引位，獲得當前迭代步驟對應的索引位圖。

6.根據權利要求5所述的方法，其特征在于，所述給預設數量的位圖位設置一個對應的索引位，具體為：

若預設數量的位圖位中至少存在一個位圖位為第一數值，則將對應的索引位設置為第一數值；若預設數量的位圖位中所有位圖位均為第二數值，則將對應的索引位設置為第二數值。

7.根據權利要求1所述的方法，其特征在于，所述根據所述索引位圖依次獲取當前迭代步驟對應的所有有用邊數據塊，具體為：

依次掃描所述索引位圖中的所有索引位，對于任意一個索引位，若該索引位為第二數值，則忽略該索引位；若該索引位為第一數值，則順序掃描該索引位對應的所有位圖位；

對于任意一個位圖位，若該位圖位為第二數值，則確定該位圖位對應的頂點為非活躍頂點，根據所述非活躍頂點的出度信息獲得該位圖位對應的無用邊數據，若該位圖位為第一數值，則確定該位圖位對應的頂點為活躍頂點，根據所述活躍頂點的出度信息獲得該位圖位對應的有用邊數據；

判斷任意兩個位圖位對應的有用邊數據之間的連續無用邊數據的大小是否超過預設閾值，若未超過所述預設閾值，則將該兩個位圖位對應的有用邊數據和所述連續無用邊數據合并為有用邊數據塊，若超過所述預設閾值，則將該兩個位圖位對應的有用邊數據分別作為單獨的有用邊數據塊。