正版新书 漫画算法与数据结构 大规模数据集 波黑 黛拉梅杰多维奇 清华大学出版社 算法分析通俗读物

当应用于大型分布式数据集时，标准算法和数据结构可能会变慢或完全失效。选择专为大数据设计的算法可以节省时间、提高准确性并降低处理成本。《漫画算法与数据结构（大规模数据集）》将最前沿的研究论文提炼为实用的技术，用于绘制、流式传输并组织磁盘和云中的大规模数据集，十分独特。

大规模数据集的算法与数据结构为大型分布式数据引入了处理和分析技术。《漫画算法与数据结构（大规模数据集）》作为指南，包含了行业故事和有趣的插图，使复杂的概念也易于理解。在学习如何将强大的算法(如Bloom 过滤器、计数最小草图、HyperLogLog和LSM树)映射到你自己的用例时，将对真实世界的示例进行探索。

主要内容：

● 概率草图数据结构

● 选择正确的数据库引擎

● 设计高效的磁盘数据结构和算法

● 大规模系统中的算法权衡

● 有限空间资源下的百分位数计算

Python、R和伪代码中的示例。

Dzejla Medjedovic在纽约石溪大学应用算法实验室获得博士学位。

Emin Tahirovic在宾夕法尼亚大学获得了生物统计学博士学位。

插图画家

Ines Dedovic在德国亚琛RWTH大学成像和计算机视觉研究所获得博士学位。

《漫画算法与数据结构（大规模数据集）》的重点并不是介绍通用的数据结构与算法分析。在大数据和人工智能的时代背景下，传统的经典算法往往性能不佳，甚至可能不起作用。本书以分布式数据集、流式数据结构与算法设计为主线，对流式数据采集、数据库中的数据结构设计、外部存储器算法进行介绍。目前，实际生产中已经形成了流式数据采集、存储、分析和计算的产品且成果显著。针对流式数据的采集和存储的产品主要有 Apache Kafka、Apache Pulsar 和 Pravega。流式数据的计算与分析主要经历了两代产品，第一代为 Apache Storm、Spark Streaming，目前流行的是第二代产品 Apache Flink。此外，还出现了 MPP(Shared Nothing 架构)的分布式并行架构数据库集群，主要有 Greenplum、HAWQ、HashData 等分布式数据库系统。通过在 MPP 架构基础上对流式数据的存储和计算支持，单节点每秒可处理多达 100 亿行数据，支持大规模数据实时写入且保证秒级实时性，主要的产品有Apache Doris、StarRocks 和 MatrixDB。这些优秀的产品无不把流式数据的数据结构和算法体现得淋漓尽致。本书针对流式数据场景，对常见的大规模数据集算法和数据结构进行了梳理和讲解。这些流式数据产品的出现有效解决了海量流式数据的采集、存储和极速全场景分析计算等问题。本书可作为从事算法设计与分析、大数据平台分析、模式识别与人工智能和数据库等领域研究工作的工程师、计算机科学家的参考书。

目 录

第Ⅰ部分基于哈希的草图

第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