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

定　價(jià)：￥129.00

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

購(gòu)買(mǎi)這本書(shū)可以去

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

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

內(nèi)容簡(jiǎn)介

　　互聯(lián)網(wǎng)的出現(xiàn)使人們第一次能夠訪問(wèn)大量的數(shù)據(jù)。比如，社交網(wǎng)絡(luò)Facebook中的友誼圖和互聯(lián)網(wǎng)網(wǎng)站之間的鏈接圖。這兩幅圖都包含超過(guò)10億個(gè)節(jié)點(diǎn)，代表巨大的數(shù)據(jù)集。如果要使用這些數(shù)據(jù)集，就必須對(duì)其進(jìn)行處理和分析。然而，僅僅是它們的大小就使得這種處理非常具有挑戰(zhàn)性。特別是，為處理中等規(guī)模的數(shù)據(jù)集而開(kāi)發(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ā)展。在本書(shū)中，我們對(duì)這項(xiàng)工作采取了計(jì)算機(jī)科學(xué)理論的觀點(diǎn)。特別是，我們將研究旨在捕捉“大數(shù)據(jù)”計(jì)算帶來(lái)的挑戰(zhàn)的計(jì)算模型，以及為應(yīng)對(duì)這些挑戰(zhàn)而開(kāi)發(fā)的實(shí)際解決方案的特性。我們將通過(guò)調(diào)查一些經(jīng)典的算法結(jié)果，包括許多最先進(jìn)的結(jié)果，來(lái)了解這些計(jì)算模型中的每一個(gè)模型。本書(shū)的設(shè)計(jì)有兩個(gè)相互矛盾的目標(biāo)，如下所示：（1）試圖在大數(shù)據(jù)背景下，給出計(jì)算機(jī)科學(xué)理論工作的一個(gè)大概的工作原理。（2）力求做到有足夠的細(xì)節(jié)，使讀者能夠參與所涵蓋主題的研究工作。

作者簡(jiǎn)介

　　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ā)表過(guò)演講。他可能領(lǐng)導(dǎo)或參與過(guò)多個(gè)研究項(xiàng)目，與業(yè)界合作伙伴共同開(kāi)發(fā)新技術(shù)或解決方案。此外，Moran Feldman教授還擔(dān)任學(xué)術(shù)委員會(huì)成員、期刊審稿人或會(huì)議組織者等職務(wù)，為學(xué)術(shù)界的發(fā)展做出了貢獻(xiàn)。

圖書(shū)目錄

第1章數(shù)據(jù)流算法簡(jiǎn)介……………………………………………………………… 1
1.1 數(shù)據(jù)流模型 ………………………………………………………………… 1
1.2 評(píng)估數(shù)據(jù)流算法 …………………………………………………………… 5
1.3 文獻(xiàn)說(shuō)明(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)說(shuō)明…………………………………………………………………… 44
練習(xí)解析 ………………………………………………………………………… 45
第4章蓄水池采樣算法 …………………………………………………………… 51
4.1 均勻抽樣…………………………………………………………………… 51
4.2 近似中值和分位數(shù)………………………………………………………… 53
4.3 加權(quán)抽樣…………………………………………………………………… 56
4.4 文獻(xiàn)說(shuō)明…………………………………………………………………… 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)說(shuō)明…………………………………………………………………… 71
練習(xí)解析 ………………………………………………………………………… 71
第6章計(jì)算不同令牌的數(shù)量 ……………………………………………………… 75
6.1 AMS算法 ………………………………………………………………… 75
6.2 一種改進(jìn)的算法…………………………………………………………… 78
6.3 不可能的結(jié)果……………………………………………………………… 82
6.4 文獻(xiàn)說(shuō)明…………………………………………………………………… 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)說(shuō)明 ………………………………………………………………… 106
練習(xí)解析………………………………………………………………………… 107
第8章圖形數(shù)據(jù)流算法…………………………………………………………… 114
8.1 概述 …………………………………………………………………… 114
8.2 最大權(quán)匹配 ……………………………………………………………… 117
8.3 三角形計(jì)數(shù) ……………………………………………………………… 125
8.4 文獻(xiàn)說(shuō)明 ………………………………………………………………… 128
練習(xí)解析………………………………………………………………………… 129
第9章滑動(dòng)窗口模型……………………………………………………………… 135
9.1 概述 …………………………………………………………………… 135
9.2 滑動(dòng)窗口模型中的圖連通性 …………………………………………… 137
9.3 平滑直方圖 ……………………………………………………………… 141
9.4 文獻(xiàn)說(shuō)明 ………………………………………………………………… 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)說(shuō)明………………………………………………………………… 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)說(shuō)明………………………………………………………………… 174
練習(xí)解析………………………………………………………………………… 175
第12章有界度圖的算法 ………………………………………………………… 182
12.1 計(jì)算連接組件數(shù)量……………………………………………………… 182
12.2 最小權(quán)生成樹(shù)…………………………………………………………… 186
12.3 最小頂點(diǎn)覆蓋…………………………………………………………… 188
12.4 測(cè)試圖形是否連通……………………………………………………… 196
12.5 文獻(xiàn)說(shuō)明………………………………………………………………… 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)說(shuō)明………………………………………………………………… 222
練習(xí)解析………………………………………………………………………… 222
第14章布爾函數(shù)的算法 ………………………………………………………… 227
14.1 模型…………………………………………………………………… 227
14.2 測(cè)試線性度……………………………………………………………… 228
14.3 單調(diào)性檢驗(yàn)……………………………………………………………… 232
14.4 文獻(xiàn)說(shuō)明………………………………………………………………… 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)說(shuō)明………………………………………………………………… 252
練習(xí)解析………………………………………………………………………… 253
第16章列表的算法 ……………………………………………………………… 256
16.1 計(jì)算 Word頻率………………………………………………………… 256
16.2 前綴和…………………………………………………………………… 259
16.3 索引…………………………………………………………………… 263
16.4 文獻(xiàn)說(shuō)明………………………………………………………………… 264
練習(xí)解析………………………………………………………………………… 264
第17章圖算法 …………………………………………………………………… 273
17.1 最小權(quán)重生成樹(shù)………………………………………………………… 273
17.2 三角形列表……………………………………………………………… 279
17.3 文獻(xiàn)說(shuō)明………………………………………………………………… 282
練習(xí)解析………………………………………………………………………… 283
第18章局部敏感哈希 …………………………………………………………… 289
18.1 主旨…………………………………………………………………… 289
18.2 局部敏感哈希函數(shù)族的示例…………………………………………… 291
18.3 放大局部敏感哈希函數(shù)族……………………………………………… 293
18.4 文獻(xiàn)說(shuō)明………………………………………………………………… 295
練習(xí)解析………………………………………………………………………… 296