零基础学大数据算法PDF电子书下载

第1篇 背景篇 4

第1章 何谓大数据 4

1.1 身边的大数据 4

1.2 大数据的特点和应用 6

第2章 何谓算法 8

2.1 算法的定义 8

2.2 算法的分析 14

2.3 基础数据结构——线性表 24

2.4 递归——以阶乘为例 28

第3章 何谓大数据算法 31

第2篇 理论篇 34

第4章 窥一斑而见全豹——亚线性算法 34

4.1 亚线性算法的定义 34

4.2 空间亚线性算法 35

4.2.1 水库抽样 35

4.2.2 数据流中的频繁元素 37

4.3 时间亚线性计算算法 40

4.3.1 图论基础回顾 40

4.3.2 平面图直径 45

4.3.3 最小生成树 46

4.4 时间亚线性判定算法 53

4.4.1 全0数组的判定 53

4.4.2 数组有序的判定 55

第5章 价钱与性能的平衡——磁盘算法 58

5.1 磁盘算法概述 58

5.2 外排序 62

5.3 外存数据结构——磁盘查找树 71

5.3.1 二叉搜索树回顾 71

5.3.2 外存数据结构——B树 78

5.3.3 高维外存查找结构——KD树 80

5.4 表排序 83

5.5 表排序的应用 86

5.5.1 欧拉回路技术 86

5.5.2 父子关系判定 87

5.5.3 前序计数 88

5.6 时间前向处理技术 90

5.7 缩图法 98

第6章 1＋1＞2——并行算法 103

6.1 MapReduce初探 103

6.2 MapReduce算法实例 106

6.2.1 字数统计 106

6.2.2 平均数计算 108

6.2.3 单词共现矩阵计算 111

6.3 MapReduce进阶算法 115

6.3.1 join操作 115

6.3.2 MapReduce图算法概述 122

6.3.3 基于路径的图算法 125

第7章 超越MapReduce的并行计算 131

7.1 MapReduce平台的局限 131

7.2 基于图处理平台的并行算法 136

7.2.1 概述 136

7.2.2 BSP模型下的单源最短路径 137

7.2.3 计算子图同构 141

第8章 众人拾柴火焰高——众包算法 144

8.1 众包概述 144

8.1.1 众包的定义 144

8.1.2 众包应用举例 146

8.1.3 众包的特点 149

8.2 众包算法例析 152

第3篇 应用篇 158

第9章 大数据中有黄金——数据挖掘 158

9.1 数据挖掘概述 158

9.2 数据挖掘的分类 159

9.3 聚类算法——k-means 160

9.4 分类算法——Naive Bayes 166

第10章 推荐系统 170

10.1 推荐系统概述 170

10.2 基于内容的推荐方法 173

10.3 协同过滤模型 176

第4篇 实践篇 186

第11章 磁盘算法实践 186

第12章 并行算法实践 194

12.1 Hadoop MapReduce实践 194

12.1.1 环境搭建 194

12.1.2 配置Hadoop 201

12.1.3 “Hello World”程序——WordCount 203

12.1.4 Hadoop实践案例——记录去重 213

12.1.5 Hadoop实践案例——等值连接 216

12.1.6 多机配置 221

12.2 适于迭代并行计算的平台——Spark 224

12.2.1 Spark初探 224

12.2.2 单词出现行计数 230

12.2.3 在Spark上实现WordCount 236

12.2.4 在HDFS上使用Spark 241

12.2.5 Spark的核心操作——Transformation和Action 244

12.2.6 Spark实践案例——PageRank 247

第13章 众包算法实践 251

13.1 认识AMT 251

13.2 成为众包工人 252