[發明專利]基于MapReduce架構實現圖處理的方法和裝置

有效

• 申請號: 201310043220.8
• 申請日: 2013-01-31
• 公開（公告）號: CN103970604B
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 史巨偉;陳冠誠;劉弢;王鯤;王晨
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 中國國際貿易促進委員會專利商標事務所11038
• 代理人: 李鎮江

1.基于MapReduce架構實現圖處理的方法，包括：

接收圖處理作業的輸入文件；

利用獲取的MapReduce任務的度數與執行時間的關系分布和所述圖處理作業的度數分布預測所述圖處理作業的MapReduce任務執行時間分布；

根據預測的所述圖處理作業的MapReduce任務執行時間分布將MapReduce任務的輸入文件切分為MapReduce任務的輸入數據分片。

2.根據權利要求1所述的方法，其中根據預測的所述圖處理作業的MapReduce任務執行時間分布將MapReduce任務的輸入文件切分為MapReduce任務的輸入數據分片包括：

檢測圖處理作業的輸入文件中的節點的鍵值對是否以該節點的度數進行構造；

響應于檢測結果為是，則按照度數對所述節點的鍵值對排序；

根據預測的所述圖處理作業的MapReduce任務執行時間分布將排序的節點的鍵值對切分為MapReduce任務的輸入數據分片。

3.根據權利要求2所述的方法，其中根據預測的所述圖處理作業的MapReduce任務執行時間分布將所述圖處理作業的輸入文件切分為輸入數據分片包括：

響應于檢測結果為否，用節點的度數對圖處理作業的輸入文件中的節點的鍵值對進行構造；

按照度數對構造后的鍵值對排序；

根據預測的所述圖處理作業的MapReduce任務執行時間分布將排序的節點的鍵值對切分為MapReduce任務的輸入數據分片。

4.根據權利要求3所述的方法，其中用節點的度數對圖處理作業的輸入文件中的節點的鍵值對進行構造包括：用節點的度數對圖處理作業的輸入文件中的節點的鍵值對的鍵值名進行構造。

5.根據權利要求2至4中任一項所述的方法，其中MapReduce任務的度數與執行時間的關系分布是Map任務的度數與執行時間的關系分布，利用獲取的MapReduce任務的度數與執行時間的關系分布和圖處理作業的度數分布預測圖處理作業的MapReduce任務執行時間分布包括利用Map任務的度數與執行時間的關系分布和圖處理作業的度數分布預測所述圖處理作業的Map任務執行時間分布。

6.根據權利要求5所述的方法，其中根據預測的所述圖處理作業的MapReduce任務執行時間分布將排序的節點的鍵值對切分為MapReduce任務的輸入數據分片包括：

根據預測的Map任務執行時間分布將排序的節點的鍵值對平均切分為Map任務的輸入數據分片；

由作業調度器將Map任務的輸入數據分片指派給Map任務服務器執行。

7.根據權利要求2至4中任一項所述的方法，其中MapReduce任務的度數與執行時間的關系分布是Reduce任務的度數與執行時間的關系分布，利用獲取的MapReduce任務的度數與執行時間的關系分布和圖處理作業的度數分布預測所述圖處理作業的MapReduce任務執行時間分布包括利用Reduce任務的度數與執行時間的關系分布和圖處理作業的度數分布預測圖處理作業的Reduce任務執行時間分布。

8.根據權利要求7所述的方法，其中根據預測的所述圖處理作業的MapReduce任務執行時間分布將排序的節點的鍵值對切分為MapReduce任務的輸入數據分片包括：

根據預測的Reduce任務執行時間分布將排序的節點的鍵值對平均切分為Reduce任務的輸入數據分片；

將Reduce任務的輸入數據分片輸入到Reduce任務的分區器；

由作業調度器將分區器輸出的輸入數據分片指派給Reduce任務服務器執行。

9.根據權利要求1所述的方法，其中MapReduce任務的度數與執行時間的關系分布是從該MapReduce任務處理的歷史記錄中獲取的，圖處理作業的度數分布是從該圖處理作業的歷史記錄中獲取的。

10.根據權利要求1所述的方法，其中MapReduce任務的度數與執行時間的關系分布是從該MapReduce任務的算法復雜度分析中獲取的。