大数据算法

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

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

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

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

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

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

                                                                                               Moran Feldman

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

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

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

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

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

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 …&hellip