《大数据算法》内容简介

大数据算法是大数据得以有效应用的基础，也是有志于从事大数据以及相关领域工作必须学习的课程。本书由从事大数据研究的专家撰写，系统地介绍了大数据算法设计与分析的理论、方法和技术。本书共分为10章，第1章概述大数据算法，第2章介绍时间亚线性算法，第3章介绍空间亚线性算法，第4章概述外存算法，第5章介绍大数据外存查找结构，第6章讲授外存图数据算法，第7章概述MapReduce算法，第8章通过一系列例子讲授MapReduce算法，第9章介绍超越MapReduce的算法设计方法，第10章讨论众包算法。
本书适合作为计算机科学、大数据等专业本科生、研究生教材，也可供从事大数据相关工作的工程技术人员参考。
王宏志是哈尔滨工业大学计算机科学与技术学院副教授、博士生导师。其研究方向为大数据、数据质量、图数据管理。发表学术论文140余篇，出版学术专著两本,出版国内首部《大数据算法》教材，其论文被SCI/EI检索80余次，他引400余次，其中5篇论文发表于顶级国际会议上。获得微软学者、中国优秀数据库工程师、IBM博士英才等称号，“海量数据计算的理论和技术”获得黑龙江省自然科学一等奖，其博士论文获得哈尔滨工业大学优秀博士论文和中国计算机学会优秀博士论文。主持各类项目十余项，包括国家自然科学基金项目3项目、国家支撑计划课题1项、国家博士后特别资助项目1项，还参加国家973项目、863项目、自然科学基金重点项目等多个项目。他担任4个国际期刊的编委，并30余次担任国内外多个知名数据库会议程序委员会委员。2014年-2015年任CCF YOCSEF哈尔滨分论坛主席，CCF高级会员，中国大数据专家委员会通信委员，中国数据库专业委员会委员，中国计算机应用专业委员会委员。在爱课程网、学堂在线、好大学在线上首次开设“大数据算法”在线课程，先后有超过30000名同学参加了这门课程的学习。

作品目录

前言
第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、连接算法
8.1.1、普通连接算法
8.1.2、相似连接算法
8.2、图算法
8.2.1、基于广度优先搜索的MapReduce图处理算法
8.2.2、PageRank的MapReduce算法
8.2.3、最小生成树的MapReduce算法
8.2.4、使用图算法的注意事项
习题
第9章：超越MapReduce的并行大数据处理
9.1、基于迭代处理平台的并行算法
9.2、基于图处理平台的并行算法
9.2.1、并行结点计算
9.2.2、并行结点计算的平台
9.2.3、基于并行结点计算的单源最短路径算法的设计与实现
9.2.4、计算子图同构
习题
第10章：众包算法
10.1、众包的定义
10.2、众包的实例
10.3、众包的要素和关键技术
10.3.1、众包的流程
10.3.2、众包的报酬
10.3.3、众包中的关键技术
10.4、众包算法例析
习题
参考文献