大数据算法

封面

版权信息

前言

第1章 绪论

1.1 大数据概述

1.1.1 什么是大数据

1.1.2 无处不在的大数据

1.1.3 大数据的特点

1.1.4 大数据的应用

1.2 大数据算法

1.2.1 大数据上求解问题的过程

1.2.2 大数据算法的定义

1.2.3 大数据的特点与大数据算法

1.2.4 大数据算法的难度

1.2.5 大数据算法的应用

1.3 大数据算法设计与分析

1.3.1 大数据算法设计技术

1.3.2 大数据算法分析技术

1.4 本书的内容

习题

第2章 时间亚线性算法

2.1 时间亚线性算法概述

2.1.1 平面图直径问题的亚线性算法

2.1.2 排序链表搜索的亚线性算法

2.1.3 两个多边形交集问题的多项式时间算法

2.2 最小生成树代价估计

2.2.1 连通分量个数估计算法

2.2.2 最小生成树代价估计算法

2.3 时间亚线性判定算法概述

2.4 数组有序的判定算法

2.5 串相等判定算法

习题

第3章 空间亚线性算法

3.1 空间亚线性算法概述

3.2 水库抽样

3.3 寻找频繁元素的非随机算法

3.3.1 频繁元素的精确解

3.3.2 频繁元素的Misra-Gries算法

3.4 估算不同元素的数量

3.4.1 基本算法

3.4.2 改进算法

3.5 寻找频繁元素的随机算法

3.5.1 略图法

3.5.2 计数-最小略图

3.6 估计频率矩

3.6.1 频率矩的AMS估计算法

3.6.2 基于拔河略图的频率矩估计

3.6.3 使用稳定分布估计范数

习题

第4章 外存算法概述

4.1 外存存储结构与外存算法概述

4.2 外存算法示例：外存排序算法

4.2.1 外存归并排序算法

4.2.2 外存多路快速排序算法

4.2.3 外存计算的下界

4.3 外存数据结构示例：外存搜索树

习题

第5章 外存查找结构

5.1 B树

5.2 加权平衡B树

5.3 持久B树

5.4 缓存树

5.5 KDB树

5.6 O树

习题

第6章 外存图数据算法

6.1 线性表排名及其应用

6.1.1 线性表排名问题

6.1.2 欧拉回路

6.1.3 父子关系判定

6.1.4 前序计数

6.1.5 计算子树大小

6.2 时间前向处理方法

6.2.1 DAG形式逻辑表达式计算问题

6.2.2 最大独立集合算法

6.3 缩图法

6.3.1 基于缩图法的图连通分量计算半外存算法

6.3.2 基于缩图法的图连通分量计算全外存算法

6.3.3 最小生成树算法

6.4 广度优先搜索和深度优先搜索

6.4.1 有向图的BFS和DFS

6.4.2 无向图的BFS

6.4.3 无向图更高效的BFS算法

6.5 单源最短路径

6.5.1 竞赛树

6.5.2 Dijkstra算法的I/O高效版本

习题

第7章 MapReduce算法概述

7.1 MapReduce基础

7.1.1 MapReduce的基本模型

7.1.2 mapper和reducer

7.1.3 partitioner与combiner

7.2 MapReduce算法设计方法

7.2.1 局部聚合

7.2.2 两种重要的算法设计模式——词对法和条块法

7.2.3 二次排序

7.2.4 MapReduce算法设计与算法实现技巧

习题

第8章 MapReduce算法例析

8.1 连接算法