CHINESE猛男吹潮GAY网站,亚洲春色av无码专区最r

互聯(lián)網(wǎng)的出現(xiàn)使人們第一次能夠訪問大量的數(shù)據(jù)。比如,社交網(wǎng)絡(luò)Facebook中的友誼圖和互聯(lián)網(wǎng)網(wǎng)站之間的鏈接圖。這兩幅圖都包含超過10億個節(jié)點,代表巨大的數(shù)據(jù)集。如果要使用這些數(shù)據(jù)集,就必須對其進(jìn)行處理和分析。然而,僅僅是它們的大小就使得這種處理非常具有挑戰(zhàn)性。特別是,為處理中等規(guī)模的數(shù)據(jù)集而開發(fā)的經(jīng)典算法和技術(shù),在面對如此大的數(shù)據(jù)集時往往需要超出常規(guī)的時間和空間。此外,在某些情況下,存儲整個數(shù)據(jù)集甚至是不可行的,因此,必須在數(shù)據(jù)集的各個部分對其進(jìn)行處理,然后很快丟棄每部分。

上述挑戰(zhàn)推動了加工處理大數(shù)據(jù)(海量數(shù)據(jù))的新工具和新技術(shù)的發(fā)展。在本書中,我們對這項工作采取了計算機(jī)科學(xué)理論的觀點。特別是,我們將研究旨在捕捉大數(shù)據(jù)計算帶來的挑戰(zhàn)的計算模型,以及為應(yīng)對這些挑戰(zhàn)而開發(fā)的實際解決方案的特性。我們將通過調(diào)查一些經(jīng)典的算法結(jié)果,包括許多最先進(jìn)的結(jié)果,來了解這些計算模型中的每一個模型。

本書的設(shè)計有兩個相互矛盾的目標(biāo),如下所示:

(1)試圖在大數(shù)據(jù)背景下,給出計算機(jī)科學(xué)理論工作的一個大概的工作原理。

(2)力求做到有足夠的細(xì)節(jié),使讀者能夠參與所涵蓋主題的研究工作。

本書的設(shè)計有兩個相互矛盾的目標(biāo),如下所示:

(1)試圖在大數(shù)據(jù)背景下,給出計算機(jī)科學(xué)理論工作的一個大概的工作原理。

(2)力求做到有足夠的細(xì)節(jié),使讀者能夠參與所涵蓋主題的研究工作。

雖然我們希望盡最大努力去實現(xiàn)這兩個目標(biāo),但我們不得不在某些方面做出妥協(xié)。特別是,我們不得不忽略一些重要的大數(shù)據(jù)主題,如降維和壓縮感知。為了使本書能被更廣泛的人群閱讀,我們還省略了一些涉及繁瑣計算和需要非常高級數(shù)學(xué)知識的經(jīng)典算法結(jié)果。在大多數(shù)情況下,這些結(jié)果的重要方面可以通過其他更容易獲得的結(jié)果來證明。

Moran Feldman

第1章數(shù)據(jù)流算法簡介……………………………………………………………… 1
1.1 數(shù)據(jù)流模型 ………………………………………………………………… 1
1.2 評估數(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)與二項分布…………………………………………………………… 19
2.4 尾界……………………………………………………………………… 20
練習(xí)解析 ………………………………………………………………………… 25
第3章估計算法 …………………………………………………………………… 35
3.1 估計流長度的莫里斯算法………………………………………………… 35
3.2 改進(jìn)估計…………………………………………………………………… 39
3.3 結(jié)束語……………………………………………………………………… 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章成對獨立的哈希函數(shù) ……………………………………………………… 65
5.1 成對哈希函數(shù)族…………………………………………………………… 65
5.2 成對獨立哈希族的簡單構(gòu)造……………………………………………… 66
5.3 成對獨立哈希族和k 向獨立哈希族的高級構(gòu)造 ……………………… 68
5.4 文獻(xiàn)說明…………………………………………………………………… 71
練習(xí)解析 ………………………………………………………………………… 71
第6章計算不同令牌的數(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 最小計數(shù)Sketches ……………………………………………………… 95
7.3 計算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 三角形計數(shù) ……………………………………………………………… 125
8.4 文獻(xiàn)說明 ………………………………………………………………… 128
練習(xí)解析………………………………………………………………………… 129
第9章滑動窗口模型……………………………………………………………… 135
9.1 概述 …………………………………………………………………… 135
9.2 滑動窗口模型中的圖連通性 …………………………………………… 137
9.3 平滑直方圖 ……………………………………………………………… 141
9.4 文獻(xiàn)說明 ………………………………………………………………… 147
練習(xí)解析………………………………………………………………………… 148
第10章次線性時間算法簡介 …………………………………………………… 154
10.1 簡單的例子……………………………………………………………… 154
10.2 估計直徑………………………………………………………………… 156
10.3 查詢復(fù)雜性……………………………………………………………… 158
10.4 文獻(xiàn)說明………………………………………………………………… 158
練習(xí)解析………………………………………………………………………… 159
第11章性能測試 ………………………………………………………………… 161
11.1 屬性測試算法…………………………………………………………… 161
11.2 測試n 個數(shù)字的列表是否有重復(fù) …………………………………… 163
11.3 列表模型和被排序列表的測試………………………………………… 166
11.4 半平面的像素模型及其檢驗…………………………………………… 169
11.5 結(jié)束語…………………………………………………………………… 173
11.6 文獻(xiàn)說明………………………………………………………………… 174
練習(xí)解析………………………………………………………………………… 175
第12章有界度圖的算法 ………………………………………………………… 182
12.1 計算連接組件數(shù)量……………………………………………………… 182
12.2 最小權(quán)生成樹…………………………………………………………… 186
12.3 最小頂點覆蓋…………………………………………………………… 188
12.4 測試圖形是否連通……………………………………………………… 196
12.5 文獻(xiàn)說明………………………………………………………………… 200
練習(xí)解析………………………………………………………………………… 201
第13章稠密圖的一種算法 ……………………………………………………… 211
13.1 模型…………………………………………………………………… 211
13.2 二部性檢驗算法………………………………………………………… 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 測試線性度……………………………………………………………… 228
14.3 單調(diào)性檢驗……………………………………………………………… 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 績效指標(biāo)………………………………………………………………… 249
15.4 不同的理論模型………………………………………………………… 251
15.5 文獻(xiàn)說明………………………………………………………………… 252
練習(xí)解析………………………………………………………………………… 253
第16章列表的算法 ……………………………………………………………… 256
16.1 計算 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

你還可能感興趣

我要評論