互联网的出现使人们第一次能够访问大量的数据。比如,社交网络Facebook中的友谊图和互联网网站之间的链接图。这两幅图都包含超过10亿个节点,代表巨大的数据集。如果要使用这些数据集,就必须对其进行处理和分析。然而,仅仅是它们的大小就使得这种处理非常具有挑战性。特别是,为处理中等规模的数据集而开发的经典算法和技术,在面对如此大的数据集时往往需要超出常规的时间和空间。此外,在某些情况下,存储整个数据集甚至是不可行的,因此,必须在数据集的各个部分对其进行处理,然后很快丢弃每部分。

上述挑战推动了加工处理大数据(海量数据)的新工具和新技术的发展。在本书中,我们对这项工作采取了计算机科学理论的观点。特别是,我们将研究旨在捕捉大数据计算带来的挑战的计算模型,以及为应对这些挑战而开发的实际解决方案的特性。我们将通过调查一些经典的算法结果,包括许多最先进的结果,来了解这些计算模型中的每一个模型。

本书的设计有两个相互矛盾的目标,如下所示:

(1)试图在大数据背景下,给出计算机科学理论工作的一个大概的工作原理。

(2)力求做到有足够的细节,使读者能够参与所涵盖主题的研究工作。

互联网的出现使人们第一次能够访问大量的数据。比如,社交网络Facebook中的友谊图和互联网网站之间的链接图。这两幅图都包含超过10亿个节点,代表巨大的数据集。如果要使用这些数据集,就必须对其进行处理和分析。然而,仅仅是它们的大小就使得这种处理非常具有挑战性。特别是,为处理中等规模的数据集而开发的经典算法和技术,在面对如此大的数据集时往往需要超出常规的时间和空间。此外,在某些情况下,存储整个数据集甚至是不可行的,因此,必须在数据集的各个部分对其进行处理,然后很快丢弃每部分。

上述挑战推动了加工处理大数据(海量数据)的新工具和新技术的发展。在本书中,我们对这项工作采取了计算机科学理论的观点。特别是,我们将研究旨在捕捉大数据计算带来的挑战的计算模型,以及为应对这些挑战而开发的实际解决方案的特性。我们将通过调查一些经典的算法结果,包括许多最先进的结果,来了解这些计算模型中的每一个模型。

本书的设计有两个相互矛盾的目标,如下所示:

(1)试图在大数据背景下,给出计算机科学理论工作的一个大概的工作原理。

(2)力求做到有足够的细节,使读者能够参与所涵盖主题的研究工作。

虽然我们希望尽最大努力去实现这两个目标,但我们不得不在某些方面做出妥协。特别是,我们不得不忽略一些重要的大数据主题,如降维和压缩感知。为了使本书能被更广泛的人群阅读,我们还省略了一些涉及繁琐计算和需要非常高级数学知识的经典算法结果。在大多数情况下,这些结果的重要方面可以通过其他更容易获得的结果来证明。

Moran Feldman

Moran Feldman教授可在计算机科学、数据科学、人工智能或相关领域拥有深厚的学术背景。他的研究兴趣可能包括算法设计、优化理论、机器学习、数据挖掘以及它们在实际应用中的部署等。在他的职业生涯中，Moran Feldman教授发表了大量高质量的学术论文，并在国际学术会议上发表过演讲。他可能领导或参与过多个研究项目，与业界合作伙伴共同开发新技术或解决方案。此外，Moran Feldman教授还担任学术委员会成员、期刊审稿人或会议组织者等职务，为学术界的发展做出了贡献。

第1章 数据流算法简介……………………………………………………………… 1
1.1 数据流模型 ………………………………………………………………… 1
1.2 评估数据流算法 …………………………………………………………… 5
1.3 文献说明(Bibliographic Notes)…………………………………………… 6
练习解析…………………………………………………………………………… 6
第2章 基本概率与尾界……………………………………………………………… 9
2.1 离散概率空间 ……………………………………………………………… 9
2.2 随机变量…………………………………………………………………… 13
2.3 指标与二项分布…………………………………………………………… 19
2.4 尾 界……………………………………………………………………… 20
练习解析 ………………………………………………………………………… 25
第3章 估计算法 …………………………………………………………………… 35
3.1 估计流长度的莫里斯算法………………………………………………… 35
3.2 改进估计…………………………………………………………………… 39
3.3 结束语……………………………………………………………………… 44
3.4 文献说明…………………………………………………………………… 44
练习解析 ………………………………………………………………………… 45
第4章 蓄水池采样算法 …………………………………………………………… 51
4.1 均匀抽样…………………………………………………………………… 51
4.2 近似中值和分位数………………………………………………………… 53
4.3 加权抽样…………………………………………………………………… 56
4.4 文献说明…………………………………………………………………… 58
练习解析 ………………………………………………………………………… 59
第5章 成对独立的哈希函数 ……………………………………………………… 65
5.1 成对哈希函数族…………………………………………………………… 65
5.2 成对独立哈希族的简单构造……………………………………………… 66
5.3 成对独立哈希族和k 向独立哈希族的高级构造 ……………………… 68
5.4 文献说明…………………………………………………………………… 71
练习解析 ………………………………………………………………………… 71
第6章 计算不同令牌的数量 ……………………………………………………… 75
6.1 AMS算法 ………………………………………………………………… 75
6.2 一种改进的算法…………………………………………………………… 78
6.3 不可能的结果……………………………………………………………… 82
6.4 文献说明…………………………………………………………………… 84
练习解析 ………………………………………………………………………… 85
第7章 Sketches …………………………………………………………………… 92
7.1 数据流模型的一般化……………………………………………………… 92
7.2 最小计数Sketches ……………………………………………………… 95
7.3 计算Sketches …………………………………………………………… 100
7.4 线性Sketches …………………………………………………………… 105
7.5 文献说明 ………………………………………………………………… 106
练习解析………………………………………………………………………… 107
第8章 图形数据流算法…………………………………………………………… 114
8.1 概 述 …………………………………………………………………… 114
8.2 最大权匹配 ……………………………………………………………… 117
8.3 三角形计数 ……………………………………………………………… 125
8.4 文献说明 ………………………………………………………………… 128
练习解析………………………………………………………………………… 129
第9章 滑动窗口模型……………………………………………………………… 135
9.1 概 述 …………………………………………………………………… 135
9.2 滑动窗口模型中的图连通性 …………………………………………… 137
9.3 平滑直方图 ……………………………………………………………… 141
9.4 文献说明 ………………………………………………………………… 147
练习解析………………………………………………………………………… 148
第10章 次线性时间算法简介 …………………………………………………… 154
10.1 简单的例子……………………………………………………………… 154
10.2 估计直径………………………………………………………………… 156
10.3 查询复杂性……………………………………………………………… 158
10.4 文献说明………………………………………………………………… 158
练习解析………………………………………………………………………… 159
第11章 性能测试 ………………………………………………………………… 161
11.1 属性测试算法…………………………………………………………… 161
11.2 测试n 个数字的列表是否有重复 …………………………………… 163
11.3 列表模型和被排序列表的测试………………………………………… 166
11.4 半平面的像素模型及其检验…………………………………………… 169
11.5 结束语…………………………………………………………………… 173
11.6 文献说明………………………………………………………………… 174
练习解析………………………………………………………………………… 175
第12章 有界度图的算法 ………………………………………………………… 182
12.1 计算连接组件数量……………………………………………………… 182
12.2 最小权生成树…………………………………………………………… 186
12.3 最小顶点覆盖…………………………………………………………… 188
12.4 测试图形是否连通……………………………………………………… 196
12.5 文献说明………………………………………………………………… 200
练习解析………………………………………………………………………… 201
第13章 稠密图的一种算法 ……………………………………………………… 211
13.1 模 型…………………………………………………………………… 211
13.2 二部性检验算法………………………………………………………… 212
13.3 减少要检查的分区数…………………………………………………… 214
13.4 取消假设………………………………………………………………… 217
13.5 文献说明………………………………………………………………… 222
练习解析………………………………………………………………………… 222
第14章 布尔函数的算法 ………………………………………………………… 227
14.1 模 型…………………………………………………………………… 227
14.2 测试线性度……………………………………………………………… 228
14.3 单调性检验……………………………………………………………… 232
14.4 文献说明………………………………………………………………… 238
练习解析………………………………………………………………………… 239
第15章 Map-Reduce概述………………………………………………………… 243
15.1 关于 Map-Reduce的一些细节 ………………………………………… 244
15.2 Map-Reduce的理论模型 ……………………………………………… 247
15.3 绩效指标………………………………………………………………… 249
15.4 不同的理论模型………………………………………………………… 251
15.5 文献说明………………………………………………………………… 252
练习解析………………………………………………………………………… 253
第16章 列表的算法 ……………………………………………………………… 256
16.1 计算 Word频率………………………………………………………… 256
16.2 前缀和…………………………………………………………………… 259
16.3 索 引…………………………………………………………………… 263
16.4 文献说明………………………………………………………………… 264
练习解析………………………………………………………………………… 264
第17章 图算法 …………………………………………………………………… 273
17.1 最小权重生成树………………………………………………………… 273
17.2 三角形列表……………………………………………………………… 279
17.3 文献说明………………………………………………………………… 282
练习解析………………………………………………………………………… 283
第18章 局部敏感哈希 …………………………………………………………… 289
18.1 主 旨…………………………………………………………………… 289
18.2 局部敏感哈希函数族的示例…………………………………………… 291
18.3 放大局部敏感哈希函数族……………………………………………… 293
18.4 文献说明………………………………………………………………… 295
练习解析………………………………………………………………………… 296