互聯(lián)網(wǎng)的出現(xiàn)使人們第一次能夠訪問大量的數(shù)據(jù)。比如,社交網(wǎng)絡(luò)Facebook中的友誼圖和互聯(lián)網(wǎng)網(wǎng)站之間的鏈接圖。這兩幅圖都包含超過10億個(gè)節(jié)點(diǎn),代表巨大的數(shù)據(jù)集。如果要使用這些數(shù)據(jù)集,就必須對(duì)其進(jìn)行處理和分析。然而,僅僅是它們的大小就使得這種處理非常具有挑戰(zhàn)性。特別是,為處理中等規(guī)模的數(shù)據(jù)集而開發(fā)的經(jīng)典算法和技術(shù),在面對(duì)如此大的數(shù)據(jù)集時(shí)往往需要超出常規(guī)的時(shí)間和空間。此外,在某些情況下,存儲(chǔ)整個(gè)數(shù)據(jù)集甚至是不可行的,因此,必須在數(shù)據(jù)集的各個(gè)部分對(duì)其進(jìn)行處理,然后很快丟棄每部分。
上述挑戰(zhàn)推動(dòng)了加工處理大數(shù)據(jù)(海量數(shù)據(jù))的新工具和新技術(shù)的發(fā)展。在本書中,我們對(duì)這項(xiàng)工作采取了計(jì)算機(jī)科學(xué)理論的觀點(diǎn)。特別是,我們將研究旨在捕捉大數(shù)據(jù)計(jì)算帶來的挑戰(zhàn)的計(jì)算模型,以及為應(yīng)對(duì)這些挑戰(zhàn)而開發(fā)的實(shí)際解決方案的特性。我們將通過調(diào)查一些經(jīng)典的算法結(jié)果,包括許多最先進(jìn)的結(jié)果,來了解這些計(jì)算模型中的每一個(gè)模型。
本書的設(shè)計(jì)有兩個(gè)相互矛盾的目標(biāo),如下所示:
(1)試圖在大數(shù)據(jù)背景下,給出計(jì)算機(jī)科學(xué)理論工作的一個(gè)大概的工作原理。
(2)力求做到有足夠的細(xì)節(jié),使讀者能夠參與所涵蓋主題的研究工作。
互聯(lián)網(wǎng)的出現(xiàn)使人們第一次能夠訪問大量的數(shù)據(jù)。比如,社交網(wǎng)絡(luò)Facebook中的友誼圖和互聯(lián)網(wǎng)網(wǎng)站之間的鏈接圖。這兩幅圖都包含超過10億個(gè)節(jié)點(diǎn),代表巨大的數(shù)據(jù)集。如果要使用這些數(shù)據(jù)集,就必須對(duì)其進(jìn)行處理和分析。然而,僅僅是它們的大小就使得這種處理非常具有挑戰(zhàn)性。特別是,為處理中等規(guī)模的數(shù)據(jù)集而開發(fā)的經(jīng)典算法和技術(shù),在面對(duì)如此大的數(shù)據(jù)集時(shí)往往需要超出常規(guī)的時(shí)間和空間。此外,在某些情況下,存儲(chǔ)整個(gè)數(shù)據(jù)集甚至是不可行的,因此,必須在數(shù)據(jù)集的各個(gè)部分對(duì)其進(jìn)行處理,然后很快丟棄每部分。
上述挑戰(zhàn)推動(dòng)了加工處理大數(shù)據(jù)(海量數(shù)據(jù))的新工具和新技術(shù)的發(fā)展。在本書中,我們對(duì)這項(xiàng)工作采取了計(jì)算機(jī)科學(xué)理論的觀點(diǎn)。特別是,我們將研究旨在捕捉大數(shù)據(jù)計(jì)算帶來的挑戰(zhàn)的計(jì)算模型,以及為應(yīng)對(duì)這些挑戰(zhàn)而開發(fā)的實(shí)際解決方案的特性。我們將通過調(diào)查一些經(jīng)典的算法結(jié)果,包括許多最先進(jìn)的結(jié)果,來了解這些計(jì)算模型中的每一個(gè)模型。
本書的設(shè)計(jì)有兩個(gè)相互矛盾的目標(biāo),如下所示:
(1)試圖在大數(shù)據(jù)背景下,給出計(jì)算機(jī)科學(xué)理論工作的一個(gè)大概的工作原理。
(2)力求做到有足夠的細(xì)節(jié),使讀者能夠參與所涵蓋主題的研究工作。
雖然我們希望盡最大努力去實(shí)現(xiàn)這兩個(gè)目標(biāo),但我們不得不在某些方面做出妥協(xié)。特別是,我們不得不忽略一些重要的大數(shù)據(jù)主題,如降維和壓縮感知。為了使本書能被更廣泛的人群閱讀,我們還省略了一些涉及繁瑣計(jì)算和需要非常高級(jí)數(shù)學(xué)知識(shí)的經(jīng)典算法結(jié)果。在大多數(shù)情況下,這些結(jié)果的重要方面可以通過其他更容易獲得的結(jié)果來證明。
Moran Feldman
Moran Feldman教授可在計(jì)算機(jī)科學(xué)、數(shù)據(jù)科學(xué)、人工智能或相關(guān)領(lǐng)域擁有深厚的學(xué)術(shù)背景。他的研究興趣可能包括算法設(shè)計(jì)、優(yōu)化理論、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘以及它們?cè)趯?shí)際應(yīng)用中的部署等。在他的職業(yè)生涯中，Moran Feldman教授發(fā)表了大量高質(zhì)量的學(xué)術(shù)論文，并在國(guó)際學(xué)術(shù)會(huì)議上發(fā)表過演講。他可能領(lǐng)導(dǎo)或參與過多個(gè)研究項(xiàng)目，與業(yè)界合作伙伴共同開發(fā)新技術(shù)或解決方案。此外，Moran Feldman教授還擔(dān)任學(xué)術(shù)委員會(huì)成員、期刊審稿人或會(huì)議組織者等職務(wù)，為學(xué)術(shù)界的發(fā)展做出了貢獻(xiàn)。
第1章 數(shù)據(jù)流算法簡(jiǎn)介……………………………………………………………… 1
1.1 數(shù)據(jù)流模型 ………………………………………………………………… 1
1.2 評(píng)估數(shù)據(jù)流算法 …………………………………………………………… 5
1.3 文獻(xiàn)說明(Bibliographic Notes)…………………………………………… 6
練習(xí)解析…………………………………………………………………………… 6
第2章 基本概率與尾界……………………………………………………………… 9
2.1 離散概率空間 ……………………………………………………………… 9
2.2 隨機(jī)變量…………………………………………………………………… 13
2.3 指標(biāo)與二項(xiàng)分布…………………………………………………………… 19
2.4 尾 界……………………………………………………………………… 20
練習(xí)解析 ………………………………………………………………………… 25
第3章 估計(jì)算法 …………………………………………………………………… 35
3.1 估計(jì)流長(zhǎng)度的莫里斯算法………………………………………………… 35
3.2 改進(jìn)估計(jì)…………………………………………………………………… 39
3.3 結(jié)束語(yǔ)……………………………………………………………………… 44
3.4 文獻(xiàn)說明…………………………………………………………………… 44
練習(xí)解析 ………………………………………………………………………… 45
第4章 蓄水池采樣算法 …………………………………………………………… 51
4.1 均勻抽樣…………………………………………………………………… 51
4.2 近似中值和分位數(shù)………………………………………………………… 53
4.3 加權(quán)抽樣…………………………………………………………………… 56
4.4 文獻(xiàn)說明…………………………………………………………………… 58
練習(xí)解析 ………………………………………………………………………… 59
第5章 成對(duì)獨(dú)立的哈希函數(shù) ……………………………………………………… 65
5.1 成對(duì)哈希函數(shù)族…………………………………………………………… 65
5.2 成對(duì)獨(dú)立哈希族的簡(jiǎn)單構(gòu)造……………………………………………… 66
5.3 成對(duì)獨(dú)立哈希族和k 向獨(dú)立哈希族的高級(jí)構(gòu)造 ……………………… 68
5.4 文獻(xiàn)說明…………………………………………………………………… 71
練習(xí)解析 ………………………………………………………………………… 71
第6章 計(jì)算不同令牌的數(shù)量 ……………………………………………………… 75
6.1 AMS算法 ………………………………………………………………… 75
6.2 一種改進(jìn)的算法…………………………………………………………… 78
6.3 不可能的結(jié)果……………………………………………………………… 82
6.4 文獻(xiàn)說明…………………………………………………………………… 84
練習(xí)解析 ………………………………………………………………………… 85
第7章 Sketches …………………………………………………………………… 92
7.1 數(shù)據(jù)流模型的一般化……………………………………………………… 92
7.2 最小計(jì)數(shù)Sketches ……………………………………………………… 95
7.3 計(jì)算Sketches …………………………………………………………… 100
7.4 線性Sketches …………………………………………………………… 105
7.5 文獻(xiàn)說明 ………………………………………………………………… 106
練習(xí)解析………………………………………………………………………… 107
第8章 圖形數(shù)據(jù)流算法…………………………………………………………… 114
8.1 概 述 …………………………………………………………………… 114
8.2 最大權(quán)匹配 ……………………………………………………………… 117
8.3 三角形計(jì)數(shù) ……………………………………………………………… 125
8.4 文獻(xiàn)說明 ………………………………………………………………… 128
練習(xí)解析………………………………………………………………………… 129
第9章 滑動(dòng)窗口模型……………………………………………………………… 135
9.1 概 述 …………………………………………………………………… 135
9.2 滑動(dòng)窗口模型中的圖連通性 …………………………………………… 137
9.3 平滑直方圖 ……………………………………………………………… 141
9.4 文獻(xiàn)說明 ………………………………………………………………… 147
練習(xí)解析………………………………………………………………………… 148
第10章 次線性時(shí)間算法簡(jiǎn)介 …………………………………………………… 154
10.1 簡(jiǎn)單的例子……………………………………………………………… 154
10.2 估計(jì)直徑………………………………………………………………… 156
10.3 查詢復(fù)雜性……………………………………………………………… 158
10.4 文獻(xiàn)說明………………………………………………………………… 158
練習(xí)解析………………………………………………………………………… 159
第11章 性能測(cè)試 ………………………………………………………………… 161
11.1 屬性測(cè)試算法…………………………………………………………… 161
11.2 測(cè)試n 個(gè)數(shù)字的列表是否有重復(fù) …………………………………… 163
11.3 列表模型和被排序列表的測(cè)試………………………………………… 166
11.4 半平面的像素模型及其檢驗(yàn)…………………………………………… 169
11.5 結(jié)束語(yǔ)…………………………………………………………………… 173
11.6 文獻(xiàn)說明………………………………………………………………… 174
練習(xí)解析………………………………………………………………………… 175
第12章 有界度圖的算法 ………………………………………………………… 182
12.1 計(jì)算連接組件數(shù)量……………………………………………………… 182
12.2 最小權(quán)生成樹…………………………………………………………… 186
12.3 最小頂點(diǎn)覆蓋…………………………………………………………… 188
12.4 測(cè)試圖形是否連通……………………………………………………… 196
12.5 文獻(xiàn)說明………………………………………………………………… 200
練習(xí)解析………………………………………………………………………… 201
第13章 稠密圖的一種算法 ……………………………………………………… 211
13.1 模 型…………………………………………………………………… 211
13.2 二部性檢驗(yàn)算法………………………………………………………… 212
13.3 減少要檢查的分區(qū)數(shù)…………………………………………………… 214
13.4 取消假設(shè)………………………………………………………………… 217
13.5 文獻(xiàn)說明………………………………………………………………… 222
練習(xí)解析………………………………………………………………………… 222
第14章 布爾函數(shù)的算法 ………………………………………………………… 227
14.1 模 型…………………………………………………………………… 227
14.2 測(cè)試線性度……………………………………………………………… 228
14.3 單調(diào)性檢驗(yàn)……………………………………………………………… 232
14.4 文獻(xiàn)說明………………………………………………………………… 238
練習(xí)解析………………………………………………………………………… 239
第15章 Map-Reduce概述………………………………………………………… 243
15.1 關(guān)于 Map-Reduce的一些細(xì)節(jié) ………………………………………… 244
15.2 Map-Reduce的理論模型 ……………………………………………… 247
15.3 績(jī)效指標(biāo)………………………………………………………………… 249
15.4 不同的理論模型………………………………………………………… 251
15.5 文獻(xiàn)說明………………………………………………………………… 252
練習(xí)解析………………………………………………………………………… 253
第16章 列表的算法 ……………………………………………………………… 256
16.1 計(jì)算 Word頻率………………………………………………………… 256
16.2 前綴和…………………………………………………………………… 259
16.3 索 引…………………………………………………………………… 263
16.4 文獻(xiàn)說明………………………………………………………………… 264
練習(xí)解析………………………………………………………………………… 264
第17章 圖算法 …………………………………………………………………… 273
17.1 最小權(quán)重生成樹………………………………………………………… 273
17.2 三角形列表……………………………………………………………… 279
17.3 文獻(xiàn)說明………………………………………………………………… 282
練習(xí)解析………………………………………………………………………… 283
第18章 局部敏感哈希 …………………………………………………………… 289
18.1 主 旨…………………………………………………………………… 289
18.2 局部敏感哈希函數(shù)族的示例…………………………………………… 291
18.3 放大局部敏感哈希函數(shù)族……………………………………………… 293
18.4 文獻(xiàn)說明………………………………………………………………… 295
練習(xí)解析………………………………………………………………………… 296
書單推薦
