新书推荐 │ 大数据算法设计与分析( 二 )

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