大规模图数据的分布式处理PDF电子书下载

第1章 大规模图数据处理：问题与挑战 1

1.1 大图数据处理的背景 1

1.2 图数据的表示 2

1.3 传统的大图数据管理方法 4

1.4 云计算环境处理大图数据的优势 6

1.5 新型大图计算系统面临的挑战 7

1.6 关键技术问题 8

第2章 大图分布式处理的计算模型和执行机制 11

2.1 大图分布式处理的基本计算框架 11

2.1.1 基于MapReduce的计算框架 11

2.1.2 基于BSP的计算框架与GAS模型 14

2.1.3 MapReduce与BSP对比 16

2.1.4 其他处理框架 17

2.2 图查询处理的遍历模式 19

2.2.1 以顶点为中心 19

2.2.2 以子图为中心 19

2.2.3 以边和路径为中心 19

2.3 消息通信 20

2.3.1 消息发送时序控制 20

2.3.2 消息交换模式 20

2.3.3 网络通信平台 22

2.3.4 上层消息优化技术 23

2.4 同步控制 23

2.4.1 同步模式 24

2.4.2 异步模式 25

2.4.3 混合模式 25

2.4.4 跨步模式 26

2.5 容错管理 26

2.5.1 故障恢复技术 26

2.5.2 故障侦测技术 30

2.6 任务调度 30

2.7 可扩展性 32

第3章 大图数据划分技术 34

3.1 图数据划分技术综述 34

3.1.1 离线划分算法 35

3.1.2 在线划分算法 36

3.1.3 动态划分算法 38

3.2 大图划分定义 41

3.2.1 处理流程和定义 41

3.2.2 真实图的局部性分析 42

3.3 OnFlyP划分算法 44

3.3.1 Range划分 44

3.3.2 OnFlyP划分 45

3.3.3 负载均衡控制机制 47

3.3.4 计算接口描述 49

3.3.5 动态调整机制 51

3.4 性能评价 52

3.5 小结 55

第4章 大图数据分布式存储与索引技术 56

4.1 大图数据的存储索引技术综述 56

4.2 图迭代算法的状态转换模型 60

4.3 大图的磁盘存储管理机制 62

4.3.1 基于列存储模型的静态Hash索引策略 62

4.3.2 基于状态转换的动态Hash索引策略 66

4.4 基于消息有序的磁盘迭代 71

4.4.1 消息有序迭代MSI 71

4.4.2 OERSV数据模型 72

4.4.3 两阶段计算过程 74

4.5 性能评价 75

4.6 小结 77

第5章 大图数据分布式三角形查询技术 78

5.1 大图三角形查询技术综述 78

5.1.1 集中式算法 79

5.1.2 分布式算法 81

5.1.3 近似算法 84

5.2 分布式大图三角形查询优化技术 84

5.2.1 存储结构 84

5.2.2 EN-Iterator算法 86

5.2.3 消息优化 87

5.3 基于采样的近似处理技术 89

5.3.1 采样策略 89

5.3.2 算法描述 91

5.4 性能评价 92

5.5 小结 95

第6章 大图数据分布式最大k边连通子图查询技术 96

6.1 大图最大k边连通子图查询技术综述 96

6.2 分布式最大k边连通子图优化技术 103

6.2.1 顶点优化 103

6.2.2 剪枝策略 104

6.2.3 消息优化 106

6.3 基于采样的近似处理技术 107

6.3.1 采样策略 107

6.3.2 算法描述 108

6.4 性能评价 109

6.5 小结 112

第7章 大图数据分布式最小生成树查询技术 113

7.1 大图数据最小生成树综述 113

7.2 顶点驱动的并行MST算法 118

7.2.1 PB算法（分区Prim算法＋Bor？vka算法） 118

7.2.2 算法正确性 119

7.2.3 双重索引 120

7.2.4 终止条件 121

7.2.5 索引维护 122

7.3 基于并行处理模型的PB算法 122

7.3.1 基于MapReduce模型的PB算法 122

7.3.2 基于BSP模型的PB算法 124

7.3.3 PB算法代价分析 124

7.4 动态图的MST维护算法 126

7.4.1 MST结果预处理 126

7.4.2 删除边维护 127

7.4.3 删除顶点维护 129

7.4.4 维护代价 129

7.5 性能评价 130

7.6 小结 132

第8章 大图数据分布式频繁子图挖掘技术 133

8.1 图数据频繁子图挖掘技术综述 133

8.1.1 图数据集中的频繁模式挖掘算法 134

8.1.2 单个大图的频繁模式挖掘算法 134

8.1.3 并行图频繁模式挖掘 136

8.2 基于最大团频繁计数的频繁子图挖掘 137

8.2.1 整体框架 137

8.2.2 挖掘频繁1-子图 140

8.2.3 候选子图产生 141

8.2.4 频繁计数 143

8.3 频繁子图挖掘分布式处理的优化 146

8.4 基于AMNI频繁计数的子图挖掘 149

8.5 频繁子图挖掘的BSP实现 151

8.6 性能评价 152

8.7 小结 155

第9章 大图数据分布式重叠社区发现技术 156

9.1 复杂网络重叠社区发现技术综述 156

9.1.1 团渗透方法 158

9.1.2 边图与边划分方法 159

9.1.3 局部扩展最优化算法 159

9.1.4 模糊检测法 160

9.1.5 基于混合概率模型算法 161

9.1.6 基于非负矩阵分解算法 161

9.1.7 其他类型算法 162

9.2 分布式并行极大团枚举 162

9.2.1 问题描述 163

9.2.2 极大团枚举方法 164

9.2.3 极大团枚举方法优化 166

9.2.4 并行极大团枚举方法 169

9.2.5 复杂度分析 172

9.3 复杂网络中并行重叠社区发现 173

9.3.1 问题描述 173

9.3.2 GCE基本算法 174

9.3.3 GCE算法的优化 175

9.3.4 GCE算法并行化 177

9.4 性能评价 183

9.5 小结 185

第10章 大规模图数据分布式处理系统和应用 186

10.1 基于MapReduce模型的大图处理系统 186

10.1.1 PECASUS 186

10.1.2 HaLoop 187

10.1.3 Twister 187

10.2 基于BSP模型的大图处理系统 188

10.2.1 Pregel 188

10.2.2 Hama 188

10.2.3 Giraph 189

10.2.4 Giraph++ 190

10.2.5 GPS 191

10.2.6 X-Pregel 191

10.2.7 Pregelix 192

10.2.8 MOCgraph 192

10.2.9 Kylin 193

10.3 其他代表性系统 193

10.3.1 PowerGraph 193

10.3.2 Trinity 194

10.3.3 GBase 194

10.3.4 Spark(GraphX) 195

10.3.5 GraphLab 195

10.3.6 Chronos 196

10.3.7 LFGraph 196

10.3.8 GraphChi、X-Stream和TurboGraph 197

10.4 BC-BSP系统介绍 200

10.4.1 体系结构概况 200

10.4.2 图处理作业的执行流程 201

10.4.3 PageRank算法示例 203

10.5 大规模图数据分布式处理的应用 207

10.5.1 Web应用 207

10.5.2 社会网络应用 210

10.5.3 生物和化学领域应用 215

参考文献 220