本书以大数据为背景，以求解大数据计算问题的计算方法（即亚线性时间计算方法、压缩计算方法、抽样计算方法、增量式计算方法、分布式并行计算方法）为主线，系统地介绍大数据计算问题求解算法的设计与分析的理论与方法，主要包括：大数据计算问题的复杂性分类、大数据计算问题的亚线性时间求解算法的设计与分析方法、基于抽样的大数据计算问题的求解算法的设计与分析方法、基于数据压缩的大数据计算问题的求解算法的设计与分析方法、大数据计算问题的增量式求解算法的设计与分析方法、大数据计算问题的分布式并行求解算法的设计与分析方法。本书以作者在大数据计算方面的研究成果为主，也覆盖了大数据算法研究领域的部分新研究成果。
本书可以作为高等学校数据科学与大数据技术专业和计算机科学与技术专业高年级本科生或研究生的大数据算法课程的教材，也可以作为大数据研究人员的参考书。

李建中，中国科学院深圳理工大学（筹）教授，哈尔滨工业大学教授，国家杰出青年基金项目获得者，是我国最早从事大数据研究的学者。研究领域包括大数据计算的复杂性理论、大数据计算方法、高效大数据算法设计与分析、大数据可用性的理论与算法。出版学术著作6部；发表学术论文500多篇，其中国际一流学术会议和一流学术期刊论文150余篇，他引2万余次，H-Index为62。主持研制多个国家急需的软件系统，获得国家和省部级科技进步奖和自然科学奖4项，其他奖励10余项，担任国际一流和重要学术会议指导委员会主席、大会主席、程序委员会主席等30余次。

第1章 绪论
1.1 大数据、大数据算法与大数据计算
1.2 大数据计算的挑战和研究问题
1.2.1 大数据计算的挑战
1.2.2 大数据计算的研究问题
1.3 大数据计算复杂性理论和算法的研究进展
1.3.1 大数据计算复杂性理论的研究进展
1.3.2 大数据算法设计方法的研究进展
1.3.3 大数据计算问题求解算法的研究进展
1.4 本章参考文献
1.4.1 本章参考文献注释
1.4.2 本章参考文献列表
第2章 大数据计算问题的复杂性
2.1 随机存取图灵机
2.1.1 确定随机存取图灵机
2.1.2 通用随机存取图灵机
2.2 大数据计算问题的复杂性与分类
2.2.1 大数据计算问题的复杂性
2.2.2 单纯易解性大数据计算问题类
2.2.3 伪易解性大数据计算问题类
2.3 归约与大数据计算问题的完全性
2.3.1 DLOGTIME归约
2.3.2 大数据计算问题的完全性
2.4 本章参考文献
2.4.1 本章参考文献注释
2.4.2 本章参考文献列表
第3章 大数据的亚线性时间计算方法
3.1 亚线性时间算法基础
3.1.1 亚线性时间算法的基本概念
3.1.2 数学基础
3.2 单纯亚线性时间精确算法
3.2.1 后继搜索算法
3.2.2 德洛奈三角剖分中的点定位算法
3.3 伪亚线性时间精确算法
3.3.1 Skyline问题的求解算法
3.3.2 Top-k支配集问题的求解算法
3.4 亚线性时间近似算法
3.4.1 最小生成树代价近似求解算法
3.4.2 数据不一致性近似评估算法
3.4.3 欧几里得空间中最近邻近似求解算法
3.5 本章参考文献
3.5.1 本章参考文献注释
3.5.2 本章参考文献列表
第4章 大数据的抽样计算方法
4.1 抽样计算方法概述
4.2 图的平均参数估计算法
4.2.1 预备知识
4.2.2 平均度求解算法
4.2.3 平均单源距离求解算法
4.2.4 平均顶点距离求解算法
4.3 无线传感网感知数据聚集算法
4.3.1 预备知识
4.3.2 基于均匀抽样的近似聚集算法
4.3.3 基于伯努利抽样的近似聚集算法
4.4 度量空间上的聚类算法
4.4.1 聚类问题的定义
4.4.2 O（n4.77）时间8-近似算法
4.4.3 时间复杂性独立于输入大小的近似算法
4.5 本章参考文献
4.5.1 本章参考文献注释
4.5.2 本章参考文献列表
第5章 大数据的压缩计算方法
5.1 压缩计算方法概述
5.2 数据压缩方法
5.2.1 数据编码方法
5.2.2 Header压缩方法
5.2.3 多维数据压缩方法
5.2.4 哈夫曼编码方法
5.3 压缩数据上的转置算法
5.3.1 问题定义
5.3.2 算法设计
5.3.3 算法分析
5.4 压缩数据上的聚集算法
5.4.1 问题定义
5.4.2 通用聚集算法
5.4.3 一遍扫描聚集算法
5.4.4 公共前缀聚集算法
5.4.5 公共中缀聚集算法
5.4.6 纯前缀聚集算法
5.5 压缩数据上的Cube算法
5.5.1 数据压缩和问题定义
5.5.2 算法设计
5.5.3 算法分析
5.6 压缩图上的可达性判定算法
5.6.1 问题定义
5.6.2 图压缩方法
5.6.3 算法设计
5.6.4 算法分析
5.7 压缩图上的图模式匹配算法
5.7.1 问题定义
5.7.2 图压缩方法
5.7.3 算法设计
5.7.4 算法分析
5.8 本章参考文献
5.8.1 本章参考文献注释
5.8.2 本章参考文献列表
第6章 大数据的增量式计算方法
6.1 增量式计算方法概述
6.2 增量式图模拟匹配算法
6.2.1 问题定义
6.2.2 图模拟匹配问题的批量求解算法
6.2.3 增量式常规图模拟匹配算法
6.2.4 增量式有界图模拟匹配算法
6.3 增量式数据不一致性检测算法
6.3.1 问题定义
6.3.2 基于数据垂直划分的检测算法
6.3.3 基于数据水平划分的检测算法
6.4 增量式数据流查询处理算法
6.4.1 问题定义
6.4.2 Inc-3-Agg类算法
6.4.3 Inc-5-Agg类算法
6.5 增量式数据流近似频繁项挖掘算法
6.5.1 问题定义
6.5.2 算法设计
6.5.3 算法的正确性与误差分析
6.5.4 算法的复杂性分析
6.6 增量式物化数据库视图维护算法
6.6.1 问题定义
6.6.2 问题的固有时间复杂性
6.6.3 算法设计
6.6.4 算法分析
6.7 本章参考文献
6.7.1 本章参考文献注释
6.7.2 本章参考文献列表
第7章 大数据的分布式并行计算方法
7.1 并行计算的基本概念
7.1.1 并行计算系统结构
7.1.2 并行算法及其复杂性分析
7.2 大数据的分布式存储方法
7.2.1 一维分布式存储方法
7.2.2 多维分布式存储方法
7.2.3 分布式Grid文件
7.2.4 分布式并行B树
7.3 分布式并行排序算法
7.3.1 基于合并操作的分布式并行排序算法
7.3.2