大数据算法设计与分析9787302602408

李建中，中国科学院深圳理工大学（筹）教授，哈尔滨工业大学教授，国家杰出青年基金获得者，国家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

 ……