【Manning新书】大规模数据结构和算法，306页pdf

2022 年 5 月 30 日 专知

海量数据集的算法和数据结构旨在帮助您构建可扩展的应用程序，并理解海量数据系统下的算法构建块。本书涵盖了构建大规模应用程序的不同算法方面，包括通过使用概率数据结构节省空间，处理流数据，处理磁盘上的数据，以及理解数据库系统中的性能权衡。

https://www.manning.com/books/algorithms-and-data-structures-for-massive-datasets#:~:text=Algorithms%20and%20Data%20Structures%20for%20Massive%20Datasets%20reveals%20a%20toolbox,truly%20massive%20amounts%20of%20data.

本书共分三个部分，共11章。第1部分是关于概率的简洁数据结构，第2部分是关于流数据结构和算法，第3部分是关于外部内存数据结构和算法。以下是每一章的简要总结:

第一章解释了为什么大量数据对现代系统提出了这样一个挑战，以及这些挑战如何塑造算法和数据结构的设计。

第1部分:概率式简洁数据结构

第二章回顾了哈希并解释了哈希表是如何发展以满足大型数据集和复杂分布式系统的需求的(例如，一致哈希)。哈希方法将在接下来的章节中大量使用，因此本章将作为第1部分其他章节的铺垫。
第三章介绍了近似隶属度问题和两个有助于解决它的数据结构:Bloom 过滤器和quotient 过滤器。本章展示了用例和假阳性率分析，以及使用每种数据结构的优缺点。
第四章描述了频率估计的问题，并介绍了countmin草图，这是一种数据结构，以非常有效的空间方式解决频率估计。讨论了NLP、传感器数据和其他领域的用例，以及计数min草图在范围查询等问题中的应用。
第五章深入了解了基数估计和HyperLog- Log算法，以及它们的应用程序。本章使用一个小型实验来展示从简单的概率计数到完整的HyperLogLog数据结构在准确性上的演变。

第2部分:流数据结构和算法

第6章温和地介绍了数据流作为一种算法概念，以及流数据(应用)作为现实世界的表现形式。通过使用流数据架构中的几个实际用例，我们展示了前几章中的数据结构如何适合流数据上下文。

第7章解释了如何从数据流或流中的滑动窗口中保存一个具有代表性的样本。我们解释了当一个人可能对一个有偏差的样本感兴趣时，并给出代码示例，展示一个样本是如何对最近看到的数据元组产生偏差的。

第8章是关于从连续数据流中计算数值数据的近似分位数。我们描述了两种草图数据结构或摘要:q-文摘和t-文摘。我们解释了它们背后的算法，并在一个真实的数据集中展示它们彼此之间的对比。

第3部分:外部内存数据结构和算法

第9章介绍了外部内存模型和一些示例，这些示例演示了在处理远程存储上的数据时，I/O成本如何支配CPU成本。这一章是一个视角转换的算法设计者习惯于思考优化算法的CPU成本。
第10章展示了支持主流数据库的数据结构，如b -树和lsm -树，并涵盖了数据库引擎设计中不同的读/写权衡。从较高的层次上理解这些数据结构是如何工作的，可以帮助您区分不同风格的数据库，并为您的应用程序选择合适的数据库。
第11章介绍了在外部内存中进行排序，并展示了使用外部内存优化版本的合并排序和快速排序在磁盘上对文件进行排序的最佳算法。第11章使用排序作为一个例子来演示当将批处理问题移动到外部内存时，哪些类型的优化是可能的。