大數(shù)據(jù)算法

定　價：￥129.00

作　者：	[以] Moran Feldman 著，祝全亮孫琳譯
出版社：	北京航空航天大學(xué)出版社
叢編項：
標(biāo)　簽：	暫缺

購買這本書可以去

當(dāng)當(dāng)網(wǎng) (￥122.60)

ISBN：	9787512442900	出版時間：	2024-04-01	包裝：	平裝-膠訂
開本：	16開	頁數(shù)：		字?jǐn)?shù)：

內(nèi)容簡介

　　互聯(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ā)展。在本書中，我們對這項工作采取了計算機科學(xué)理論的觀點。特別是，我們將研究旨在捕捉“大數(shù)據(jù)”計算帶來的挑戰(zhàn)的計算模型，以及為應(yīng)對這些挑戰(zhàn)而開發(fā)的實際解決方案的特性。我們將通過調(diào)查一些經(jīng)典的算法結(jié)果，包括許多最先進(jìn)的結(jié)果，來了解這些計算模型中的每一個模型。本書的設(shè)計有兩個相互矛盾的目標(biāo)，如下所示：（1）試圖在大數(shù)據(jù)背景下，給出計算機科學(xué)理論工作的一個大概的工作原理。（2）力求做到有足夠的細(xì)節(jié)，使讀者能夠參與所涵蓋主題的研究工作。

作者簡介

　　Moran Feldman教授可在計算機科學(xué)、數(shù)據(jù)科學(xué)、人工智能或相關(guān)領(lǐng)域擁有深厚的學(xué)術(shù)背景。他的研究興趣可能包括算法設(shè)計、優(yōu)化理論、機器學(xué)習(xí)、數(shù)據(jù)挖掘以及它們在實際應(yīng)用中的部署等。在他的職業(yè)生涯中，Moran Feldman教授發(fā)表了大量高質(zhì)量的學(xué)術(shù)論文，并在國際學(xué)術(shù)會議上發(fā)表過演講。他可能領(lǐng)導(dǎo)或參與過多個研究項目，與業(yè)界合作伙伴共同開發(fā)新技術(shù)或解決方案。此外，Moran Feldman教授還擔(dān)任學(xué)術(shù)委員會成員、期刊審稿人或會議組織者等職務(wù)，為學(xué)術(shù)界的發(fā)展做出了貢獻(xiàn)。

圖書目錄

第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 隨機變量…………………………………………………………………… 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