《大規模圖數據的高效計算關鍵技術研究》是2020年清華大學出版社出版的圖書，作者是章明星。
基本介紹
- 中文名：大規模圖數據的高效計算關鍵技術研究
- 作者：章明星
- 出版社：清華大學出版社
- 出版時間：2020年5月1日
- 定價：89 元
- ISBN：9787302542537
內容簡介,圖書目錄,
內容簡介
由於具有良好的表達能力，圖數據結構被廣泛用來對元素間具有複雜聯繫的數據進行建模，如社交網路、知識圖譜等。因此，可以對大規模圖數據進行分析的處理技術逐漸成為當前學術界和業界的熱門研究話題之一。目前，已有為數眾多的圖計算系統被提出和套用，並取得了巨大的商業成功。本書通過將不同環境下圖計算系統的數據載入途徑分為四個階段分別進行了研究，總結出了一系列的最佳化方法，可為相關研究人員提供參考。
圖書目錄
第 1章引言 .......................................................................................1
1.1大規模圖計算 .........................................................................1
1.2圖計算系統的分類 ...................................................................2
1.3圖數據高效計算的挑戰 ............................................................5
1.3.1圖計算的特點 ...............................................................6
1.3.2現狀和主要最佳化方向 .....................................................7
1.4主要貢獻 ................................................................................9
1.5本書組織結構 ....................................................................... 11
第 2章相關工作 ............................................................................... 13
2.1基於分散式集群的圖計算系統 ................................................ 13
2.1.1分散式圖計算中的基本概念 ......................................... 13
2.1.2分散式圖計算中任務的劃分算法 .................................. 15
2.2基於外存的圖計算系統 .......................................................... 18
2.2.1外存圖計算系統的意義和挑戰 ..................................... 18
2.2.2以點為中心的外存圖計算系統 ..................................... 20
2.2.3以邊為中心的外存圖計算系統 ..................................... 21
2.3基於矩陣的圖計算引擎 .......................................................... 23
2.4基於存算融合硬體的圖計算系統 ............................................. 26
第 3章分散式圖計算系統的三維任務劃分 .......................................... 31
3.1概述 ..................................................................................... 31
3.2實例研究：協同過濾問題 ....................................................... 33
3.3三維劃分的基本概念 ............................................................. 34
3.4三維劃分下的編程模型 .......................................................... 37
3.4.1數據模型 ................................................................... 37
3.4.2 UPPS下的三維劃分 ................................................... 39
3.4.3計算模型 ................................................................... 40
3.4.4二部圖 ....................................................................... 41
3.4.5與 GAS模型的比較 .................................................... 41
3.4.6例程 .......................................................................... 42
3.5系統實現 .............................................................................. 47
3.5.1數據載入和劃分 ......................................................... 47
3.5.2 Update操作的實現 .................................................... 48
3.5.3 Push，Pull和 Sink操作的實現 ................................... 49
3.5.4基於矩陣的數據結構 ................................................... 49
3.6實驗結果 .............................................................................. 50
3.6.1測試環境 ................................................................... 51
3.6.2微型測試集 ................................................................ 52
3.6.3實際套用 ................................................................... 57
3.6.4其他討論 ................................................................... 62
3.7小結 ..................................................................................... 66
第 4章外存圖計算系統的分層數據組織 ............................................. 67
4.1概述 ..................................................................................... 67
4.2背景介紹 .............................................................................. 69
4.2.1外存圖計算系統中的一維劃分： GraphChi .................... 69
4.2.2外存圖計算系統中的二維劃分： GridGraph.................... 70
4.3 3DGridGraph ........................................................................ 72
4.3.1分層存儲優勢 ............................................................. 72
4.3.2編程模型 ................................................................... 74
4.3.3實例研究 ................................................................... 75
4.3.4實現 .......................................................................... 76
4.4測試結果 .............................................................................. 77
4.4.1定量分析 ................................................................... 77
目錄 15
4.4.2實測結果 ................................................................... 78
4.5小結 ..................................................................................... 79
第 5章矩陣計算引擎的自動最佳化 ....................................................... 81
5.1概述 ..................................................................................... 81
5.1.1背景介紹 ................................................................... 81
5.1.2挑戰 .......................................................................... 82
5.1.3我們的工作 ................................................................ 83
5.2設計思路與原理 .................................................................... 84
5.3 Kasen的編程模型 ................................................................ 86
5.3.1數據 .......................................................................... 86
5.3.2數據的操作 ................................................................ 87
5.3.3實例： PageRank ........................................................ 89
5.3.4套用範圍 ................................................................... 90
5.4 Kasen模型的具體實現 ......................................................... 91
5.4.1三種數據存儲狀態 ...................................................... 91
5.4.2顯式的存儲狀態轉化 ................................................... 93
5.4.3約束條件 ................................................................... 94
5.5最佳化方法 .............................................................................. 96
5.5.1循環融合 ................................................................... 96
5.5.2內部操作 ................................................................... 98
5.5.3 DDAG...................................................................... 100
5.5.4最佳化算法 ................................................................. 101
5.5.5實例研究 ................................................................. 104
5.6估算公式 ............................................................................ 105
5.7實現細節 ............................................................................ 107
5.8性能測試 ............................................................................ 108
5.8.1定量分析 ................................................................. 108
5.8.2性能測試 ................................................................. 110
5.8.3與已有系統的性能對比 ............................................. 112
5.9小結 ................................................................................... 113
第 6章拓撲感知的存算融合圖計算方法 ........................................... 115
6.1概述 ................................................................................... 115
6.2背景介紹 ............................................................................ 118
6.2.1互聯拓撲結構 ........................................................... 118
6.2.2網路瓶頸 ................................................................. 120
6.2.3已有的 PIM圖計算系統 ............................................ 121
6.3 PGIM系統 ........................................................................ 123
6.3.1兩階段點程式 ........................................................... 123
6.3.2廣播 ........................................................................ 128
6.3.3計算和通訊的重合 .................................................... 129
6.4測試 ................................................................................... 129
6.4.1劃分對通訊量的影響 ................................................. 130
6.4.2廣播對瓶頸鏈路通訊量的影響 ................................... 131
6.5小結 ................................................................................... 131
第 7章總結與展望 ......................................................................... 133
7.1總結 ................................................................................... 133
7.2展望 ................................................................................... 134
參考文獻 ........................................................................................... 137
在學期間發表的學術論文與研究成果 ................................................... 145
致謝 .................................................................................................. 147
