漫画算法与数据结构(大规模数据集)

第Ⅰ部分基于哈希的草图
第1 章 导论 3
1.1 示例 5
1.1.1 示例解决方法 6
1.1.2 本书给出的解决方法 8
1.2 本书的结构 11
1.3 本书的不同之处及目标读者 12
1.4 为什么大规模数据对当今的系统如此具有挑战性 13
1.4.1 CPU 内存性能差距 13
1.4.2 内存层次结构 14
1.4.3 延迟与带宽 15
1.4.4 分布式系统的情况 15
1.5 基于硬件来设计算法 16
1.6 本章小结 17
第2 章 哈希表和现代哈希回顾 19
2.1 无处不在的哈希 20
2.2 数据结构概述 22
2.3 现代系统中的使用场景 25
2.3.1 备份/存储解决方案中的重复数据删除 25
2.3.2 使用MOSS 和Rabin-Karp 指纹识别进行剽窃检测 26
2.4 有关O(1) 29
2.5 解决冲突：理论与实践 30
2.6 使用场景：Python 的dict是如何实现的 33
2.7 MurmurHash 35
2.8 分布式系统的哈希表：一致性哈希 36
2.8.1 一个典型的哈希问题 37
2.8.2 哈希环 38
2.8.3 查找 41
2.8.4 添加新节点/资源 41
2.8.5 删除节点 44
2.8.6 一致性哈希场景：Chord 48
2.8.7 一致性哈希：编程练习 50
2.9 本章小结 50
第3 章 近似成员关系：Bloom 过滤器和商
过滤器 53
3.1 工作原理 56
3.1.1 插入 56
3.1.2 查找 57
3.2 用例 58
3.2.1 网络中的Bloom 过滤器：Squid 58
3.2.2 Bitcoin 移动应用 59
3.3 一个简单的实现 60
3.4 设置Bloom过滤器 61
3.5 一点理论 66
3.6 Bloom 过滤器的调整和替代方案 69
3.7 商过滤器 70
3.7.1 商-余数法 71
3.7.2 了解元数据位 73
3.7.3 示例：插入商过滤器中 73
3.7.4 用于查找的Python代码 76
3.7.5 调整大小与合并 79
3.7.6 误报率和空间考虑 80
3.8 Bloom 过滤器和商过滤器的比较 80
3.9 本章小结 82
第4 章 频率估计和count-minsketch 85
4.1 多数元素 87
4.2 count-min sketch 的工作原理 90
4.2.1 update 90
4.2.2 estimate 91
4.3 用例 92
4.3.1 前k 个睡眠不安者 92
4.3.2 缩放单词的分布相似度 96
4.4 count-min sketch 中的误差与空间 99
4.5 count-min sketch 的简单实现 100
4.5.1 练习 101
4.5.2 公式所蕴含的原理 102
4.6 使用count-min sketch进行范围查询 103
4.6.1 二元区间 104
4.6.2 更新阶段 105
4.6.3 估计阶段 107
4.6.4 计算二元区间 108
4.7 本章小结 110
第5 章 基数估计和HyperLogLog 113
5.1 对数据库中的不同项计数 114
5.2 HyperLogLog 增量设计 116
5.2.1 **步：概率计数 117
5.2.2 随机平均 119
5.2.3 LogLog 121
5.2.4 HyperLogLog：使用调和平均值进行随机平均 123
5.3 用例：使用HLL 捕捉蠕虫 126
5.4 一个小实验 128
5.5 用例：使用Hyper-LogLog 进行聚合 132
5.6 本章小结 135
第Ⅱ部分实时分析第6 章 流式数据 139
6.1 流式数据系统：元示例 144
6.1.1 Bloom 连接 144
6.1.2 重复数据删除 147
6.1.3 负载平衡和跟踪网络流量 149
6.2 数据流中的实际约束和概念 151
6.2.1 实时 151
6.2.2 小时间和小空间 152
6.2.3 概念转变和概念漂移 152
6.2.4 滑动窗口模型 153
6.3 抽样和估计 155
6.3.1 有偏差抽样策略 157
6.3.2 代表性样本的估计 160
6.4 本章小结 162
第7 章 从数据流中抽样 165
7.1 从地标流中抽样 166
7.1.1 伯努利抽样 166
7.1.2 蓄水池抽样 170
7.1.3 有偏差的蓄水池抽样 176
7.2 从滑动窗口抽样 182
7.2.1 链式抽样 182
7.2.2 优先级抽样 187
7.3 抽样算法比较 191
7.4 本章小结 195
第8 章 数据流上的近似分位数 197
8.1 精确分位数 198
8.2 近似分位数 201
8.2.1 加法误差 201
8.2.2 相对误差 203
8.2.3 数据域中的相对误差 204
8.3 t-digest：工作
原理 204
8.3.1 digest 205
8.3.2 比例函数 207
8.3.3 合并t-digest 211
8.3.4 t-digest 的空间范围 215
8.4 q-digest 215
8.4.1 从头开始构建q-digest 216
8.4.2 合并q-digest 218
8.4.3 q-digest 中的误差和空间注意事项 219
8.4.4 使用q-digest 进行分位数查询 220
8.5 模拟代码和结果 221
8.6 本章小结 226
第Ⅲ部分数据库的数据结构和外部存储器算法 第9 章 外部存储器模型 231
9.1 外部存储器模型初探 233
9.2 示例1：寻找*小值 235
9.3 示例2：二进制搜索 239
9.3.1 生物信息学用例 239
9.3.2 运行时间分析 241
9.4 *优搜索 243
9.5 示例3：合并K 个排序列表 246
9.5.1 合并时间/日期日志 246
9.5.2 外部存储器模型是否过于简单 250
9.6 下一章内容 251
9.7 本章小结 251
第10 章 数据库的数据结构：B 树、Bε 树和LSM 树 253
10.1 索引的工作原理 254
10.2 本章中的数据结构 256
10.3 B 树 258
10.3.1 B 树平衡 259
10.3.2 查找 260
10.3.3 插入 261
10.3.4 删除 263
10.3.5 B 树 266
10.3.6 B 树上的操作有何不同 268
10.3.7 用例：MySQL 等中的B 树 268
10.4 为什么B 树查找在外部存储器中是*佳的 269
10.5 Bε 树 272
10.5.1 Bε 树：工作原理 273
10.5.2 缓冲区机制· 273
10.5.3 插入和删除 275
10.5.4 查找 276
10.5.5 成本分析 277
10.5.6 Bε 树：数据结构的范围 278
10.5.7 用例：TokuDB 中的Bε 树 279
10.5.8 输入/输出之道：欲速则不达 280
10.6 日志结构合并树(LSM 树) 281
10.6.1 LSM 树：工作原理 283
10.6.2 LSM 树成本分析 285
10.6.3 用例：Cassandra 中的LSM 树 286
10.7 本章小结 287
第11 章 外部存储器排序 289
11.1 排序用例 290
11.1.1 机器人运动规划 290
11.1.2 癌症基因组学 291
11.2 外部存储器排序的挑战：示例 293
11.3 外部存储器合并排序 297
11.4 外部快速排序 300
11.4.1 外部存储器双向快速排序 301
11.4.2 外部存储器多向快速排序 302
11.4.3 找到足够的枢轴 303
11.4.4 找到足够好的枢轴 304
11.4.5 将它们重新组合在一起 305
11.5 为什么外部存储器合并排序是*优的 306
11.6 结尾 308
11.7 本章小结 309
参考文献 310