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

第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