大规模图数据的分布式处理

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

1.1大图数据处理的背景

1.2图数据的表示

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

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

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

1.6关键技术问题

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

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

2.1.1基于MapReduce的计算框架

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

2.1.3MapReduce与BSP对比

2.1.4其他处理框架

2.2图查询处理的遍历模式

2.2.1以顶点为中心

2.2.2以子图为中心

2.2.3以边和路径为中心

2.3消息通信

2.3.1消息发送时序控制

2.3.2消息交换模式

2.3.3网络通信平台

2.3.4上层消息优化技术

2.4同步控制

2.4.1同步模式

2.4.2异步模式

2.4.3混合模式

2.4.4跨步模式

2.5容错管理

2.5.1故障恢复技术

2.5.2故障侦测技术

2.6任务调度

2.7可扩展性

第3章大图数据划分技术

3.1图数据划分技术综述

3.1.1离线划分算法

3.1.2在线划分算法

3.1.3动态划分算法

3.2大图划分定义

3.2.1处理流程和定义

3.2.2真实图的局部性分析

3.3OnFlyP划分算法

3.3.1Range划分

3.3.2OnFlyP划分

3.3.3负载均衡控制机制

3.3.4计算接口描述

3.3.5动态调整机制

3.4性能评价

3.5小结

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

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

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

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

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

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

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

4.4.1消息有序迭代MSI

4.4.2OERSV数据模型

4.4.3两阶段计算过程

4.5性能评价

4.6小结

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

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

5.1.1集中式算法

5.1.2分布式算法

5.1.3近似算法

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

5.2.1存储结构

5.2.2EN-Iterator算法

5.2.3消息优化

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

5.3.1采样策略

5.3.2算法描述

5.4性能评价

5.5小结

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

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

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

6.2.1顶点优化

6.2.2剪枝策略

6.2.3消息优化

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

6.3.1采样策略

6.3.2算法描述

6.4性能评价

6.5小结

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

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

7.2顶点驱动的并行MST算法

7.2.1PB算法（分区Prim算法+Borvka算法）

7.2.2算法正确性

7.2.3双重索引

7.2.4终止条件

7.2.5索引维护

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

7.3.1基于MapReduce模型的PB算法

7.3.2基于BSP模型的PB算法

7.3.3PB算法代价分析

7.4动态图的MST维护算法

7.4.1MST结果预处理

7.4.2删除边维护

7.4.3删除顶点维护

7.4.4维护代价

7.5性能评价

7.6小结

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

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

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

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

8.1.3并行图频繁模式挖掘

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

8.2.1整体框架

8.2.2挖掘频繁1-子图

8.2.3候选子图产生

8.2.4频繁计数

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

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

8.5频繁子图挖掘的BSP实现

8.6性能评价

8.7小结

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

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

9.1.1团渗透方法

9.1.2边图与边划分方法

9.1.3局部扩展最优化算法

9.1.4模糊检测法

9.1.5基于混合概率模型算法

9.1.6基于非负矩阵分解算法

9.1.7其他类型算法

9.2分布式并行极大团枚举

9.2.1问题描述

9.2.2极大团枚举方法

9.2.3极大团枚举方法优化

9.2.4并行极大团枚举方法

9.2.5复杂度分析

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

9.3.1问题描述

9.3.2GCE基本算法

9.3.3GCE算法的优化

9.3.4GCE算法并行化

9.4性能评价

9.5小结

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

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

10.1.1PEGASUS

10.1.2HaLoop

10.1.3Twister

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

10.2.1Pregel

10.2.2Hama

10.2.3Giraph

10.2.4Giraph++

10.2.5GPS

10.2.6X-Pregel

10.2.7Pregelix

10.2.8MOCgraph

10.2.9Kylin

10.3其他代表性系统

10.3.1PowerGraph

10.3.2Trinity

10.3.3GBase

10.3.4Spark（GraphX）

10.3.5GraphLab

10.3.6Chronos

10.3.7LFGraph

10.3.8GraphChi、X-Stream和TurboGraph

10.4BC-BSP系统介绍

10.4.1体系结构概况

10.4.2图处理作业的执行流程

10.4.3PageRank算法示例

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

10.5.1Web应用

10.5.2社会网络应用

10.5.3生物和化学领域应用

参考文献

随着以社交网络为代表的图数据规模高速增长，复杂的查询需求不断涌现，处理这类大规模数据有许多理论问题需要解决。本书结合作者多年的研究积累，系统地介绍了大图分布式处理中基础的数据划分、组织和消息管理技术，以及三角形、最大k边连通子图、最小生成树、频繁子图、重叠社区发现等大图查询和分析算法的优化，并对系统实现技术进行了探讨。本书适合高等院校计算机专业的教师、学生及计算机应用系统的研发人员阅读参考。