大数据算法设计与分析

"《大数据算法设计与分析》以大数据基础研究与大数据应用为背景，以大数据算法设计与分析方法学为主线，以多个重要大数据计算问题为例，全面、系统、深入地介绍大数据算法设计与分析的原理与方法。 ? 著作的内容包括大数据算法方面的近期新和最重要研究成果，全面反映大数据算法研究的新进展。 ? 著作注重理论与实际相结合，以具有实际应用背景的大数据计算问题为例，既细致地介绍其求解算法的设计方法，又对算法的正确属性和复杂性进行精致的理论分析，使得读者不仅掌握求解重要大数据计算问题的大数据算法的设计和分析方法，同时建立坚实的大数据算法设计与分析的基础理论，不但具有解决实际应用领域的大数据问题的求解算法的设计和分析能力，也具有从事大数据算法设计与分析的基础研究的创新能力。 ? 著作既能够满足大数据基础研究者和应用开发者的需要，也能满足数据科学与大数据技术专业研究生的教学需要，还能通过适当内容选择满足数据科学与大数据技术专业本科生的教学需要。 "

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

李建中，中国科学院深圳理工大学（筹）教授，哈尔滨工业大学教授，国家杰出青年基金获得者，国家973项目首席科学家。主要从事大数据计算等研究，主持完成国家973计划、国家863计划、国家自然科学基金重大与重点等项目20余项，在不错学术期刊和会议发表120余篇论文，他引2万余次，H-index 50，并研制了多个计算机软硬件系统，多次获得重量和省部级科技进步和自然科学奖。

第1章绪论1
1.1大数据、大数据算法与大数据计算2
1.2大数据计算的挑战和研究问题3
1.2.1大数据计算的挑战3
1.2.2大数据计算的研究问题6
1.3大数据计算复杂性理论和算法的研究进展7
1.3.1大数据计算复杂性理论的研究进展7
1.3.2大数据算法设计方法的研究进展10
1.3.3大数据计算问题求解算法的研究进展12
1.4本章参考文献17
1.4.1本章参考文献注释17
1.4.2本章参考文献列表17
第2章大数据计算问题的复杂性26
2.1随机存取图灵机26
2.1.1确定随机存取图灵机26
2.1.2通用随机存取图灵机29
2.2大数据计算问题的复杂性与分类33
2.2.1大数据计算问题的复杂性33
2.2.2单纯易解性大数据计算问题类35
2.2.3伪易解性大数据计算问题类39
2.3归约与大数据计算问题的接近性41
2.3.1DLOGTIME归约41
2.3.2大数据计算问题的接近性44
2.4本章参考文献44
2.4.1本章参考文献注释44
2.4.2本章参考文献列表45
第3章大数据的亚线性时间计算方法46
3.1亚线性时间算法基础46
3.1.1亚线性时间算法的基本概念46
3.1.2数学基础50
3.2单纯亚线性时间准确算法54
3.2.1后继搜索算法54
3.2.2德洛奈三角剖分中的点定位算法56
3.3伪亚线性时间准确算法62
3.3.1Skyline问题的求解算法62
3.3.2Top-k支配集问题的求解算法66
3.4亚线性时间近似算法75
3.4.1最小生成树代价近似求解算法76
3.4.2数据不一致性近似评估算法83
3.4.3欧几里得空间中最近邻近似求解算法91
3.5本章参考文献102
3.5.1本章参考文献注释102
3.5.2本章参考文献列表103
第4章大数据的抽样计算方法105
4.1抽样计算方法概述105
4.2图的平均参数估计算法106
4.2.1预备知识106
4.2.2平均度求解算法108
4.2.3平均单源距离求解算法113
4.2.4平均顶点距离求解算法115
4.3无线传感网感知数据聚集算法118
4.3.1预备知识118
4.3.2基于均匀抽样的近似聚集算法121
4.3.3基于伯努利抽样的近似聚集算法137
4.4度量空间上的聚类算法148
4.4.1聚类问题的定义148
4.4.2O(n4.77)时间8-近似算法149
4.4.3时间复杂性独立于输入大小的近似算法162
4.5本章参考文献171
4.5.1本章参考文献注释171
4.5.2本章参考文献列表172
第5章大数据的压缩计算方法173
5.1压缩计算方法概述173
5.2数据压缩方法175
5.2.1数据编码方法176
5.2.2Header压缩方法179
5.2.3多维数据压缩方法184
5.2.4哈夫曼编码方法186
5.3压缩数据上的转置算法190
5.3.1问题定义190
5.3.2算法设计191
5.3.3算法分析192
5.4压缩数据上的聚集算法194
5.4.1问题定义194
5.4.2通用聚集算法195
5.4.3一遍扫描聚集算法199
5.4.4公共前缀聚集算法200
5.4.5公共中缀聚集算法203
5.4.6纯前缀聚集算法206
5.5压缩数据上的Cube算法207
5.5.1数据压缩和问题定义207
5.5.2算法设计208
5.5.3算法分析220
5.6压缩图上的可达性判定算法224
5.6.1问题定义224
5.6.2图压缩方法225
5.6.3算法设计227
5.6.4算法分析228
5.7压缩图上的图模式匹配算法229
5.7.1问题定义229
5.7.2图压缩方法230
……