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

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

第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生物和化学领域应用
参考文献