大数据算法设计与分析

第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

〖1〗〖1〗第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

5.7.3算法设计235

5.7.4算法分析235

5.8本章参考文献236

5.8.1本章参考文献注释236

5.8.2本章参考文献列表237

第6章大数据的增量式计算方法238

6.1增量式计算方法概述238

6.2增量式图模拟匹配算法241

6.2.1问题定义241

6.2.2图模拟匹配问题的批量求解算法246

6.2.3增量式常规图模拟匹配算法251

6.2.4增量式有界图模拟匹配算法260

6.3增量式数据不一致性检测算法266

6.3.1问题定义266

6.3.2基于数据垂直划分的检测算法270

6.3.3基于数据水平划分的检测算法274

6.4增量式数据流查询处理算法278

6.4.1问题定义278

6.4.2Inc3Agg类算法280

6.4.3Inc5Agg类算法282

6.5增量式数据流近似频繁项挖掘算法286

6.5.1问题定义287

6.5.2算法设计287

6.5.3算法的正确性与误差分析289

6.5.4算法的复杂性分析290

6.6增量式物化数据库视图维护算法290

6.6.1问题定义290

6.6.2问题的固有时间复杂性291

6.6.3算法设计296

6.6.4算法分析297

6.7本章参考文献299

6.7.1本章参考文献注释299

6.7.2本章参考文献列表300

第7章大数据的分布式并行计算方法301

7.1并行计算的基本概念301

7.1.1并行计算系统结构301

7.1.2并行算法及其复杂性分析306

7.2大数据的分布式存储方法308

7.2.1一维分布式存储方法308

7.2.2多维分布式存储方法311

7.2.3分布式Grid文件316

7.2.4分布式并行B树324

7.3分布式并行排序算法330

7.3.1基于合并操作的分布式并行排序算法331

7.3.2基于比较交换的分布式并行排序算法333

7.3.3基于数据划分的分布式并行排序算法335

7.4集合操作的分布式并行算法338

7.4.1集合并的分布式并行算法338

7.4.2集合交的分布式并行算法339

7.4.3集合差的分布式并行算法340

7.5关系代数操作的分布式并行算法341

7.5.1选择操作的分布式并行算法341

7.5.2投影操作的分布式并行算法344

7.5.3连接操作的分布式并行算法346

7.6基于CMD的连接操作的分布式并行连接算法351

7.6.1基本概念351

7.6.2算法CMDJoinHash353

7.6.3算法CMDJoinSortMerge354

7.6.4算法CMDJoinNestedLoop356

7.7基于并行B树的连接操作的分布式并行算法357

7.7.1预备知识357

7.7.2基于Range分布方法的并行B树连接算法357

7.7.3基于Hash分布方法的并行B树连接算法362

7.8本章参考文献364

7.8.1本章参考文献注释364

7.8.2本章参考文献列表365