目錄
前　　言
第1章　緒論1
1.1　大數據概述1
1.1.1　什麼是大數據1
1.1.2　無處不在的大數據1
1.1.3　大數據的特點3
1.1.4　大數據的應用4
1.2　大數據算法5
1.2.1　大數據上求解問題的過程6
1.2.2　大數據算法的定義7
1.2.3　大數據的特點與大數據算法9
1.2.4　大數據算法的難度9
1.2.5　大數據算法的應用10
1.3　大數據算法設計與分析11
1.3.1　大數據算法設計技術11
1.3.2　大數據算法分析技術12
1.4　本書的內容13
習題13
第2章　時間亞綫性算法14
2.1　時間亞綫性算法概述14
2.1.1　平麵圖直徑問題的亞綫性算法14
2.1.2　排序鏈錶搜索的亞綫性算法16
2.1.3　兩個多邊形交集問題的多項式時間算法17
2.2　最小生成樹代價估計18
2.2.1　連通分量個數估計算法18
2.2.2　最小生成樹代價估計算法20
2.3　時間亞綫性判定算法概述23
2.4　數組有序的判定算法25
2.5　串相等判定算法27
習題28
第3章　空間亞綫性算法29
3.1　空間亞綫性算法概述29
3.2　水庫抽樣31
3.3　尋找頻繁元素的非隨機算法32
3.3.1　頻繁元素的精確解33
3.3.2　頻繁元素的Misra-Gries算法33
3.4　估算不同元素的數量35
3.4.1　基本算法35
3.4.2　改進算法38
3.5　尋找頻繁元素的隨機算法42
3.5.1　略圖法42
3.5.2　計數最小略圖45
3.6　估計頻率矩47
3.6.1　頻率矩的AMS估計算法47
3.6.2　基於拔河略圖的頻率矩估計51
3.6.3　使用穩定分布估計範數53
習題57
第4章　外存算法概述60
4.1　外存存儲結構與外存算法概述60
4.2　外存算法示例：外存排序算法64
4.2.1　外存歸並排序算法64
4.2.2　外存多路快速排序算法68
4.2.3　外存計算的下界74
4.3　外存數據結構示例：外存搜索樹77
習題78
第5章　外存查找結構80
5.1　B樹80
5.2　加權平衡B樹87
5.3　持久B樹90
5.4　緩存樹94
5.5　KDB樹98
5.6　O樹103
習題107
第6章　外存圖數據算法109
6.1　綫性錶排名及其應用109
6.1.1　綫性錶排名問題109
6.1.2　歐拉迴路114
6.1.3　父子關係判定115
6.1.4　前序計數116
6.1.5　計算子樹大小117
6.2　時間前嚮處理方法117
6.2.1　DAG形式邏輯錶達式計算問題118
6.2.2　最大獨立集閤算法121
6.3　縮圖法124
6.3.1　基於縮圖法的圖連通分量計算半外存算法124
6.3.2　基於縮圖法的圖連通分量計算全外存算法126
6.3.3　最小生成樹算法128
6.4　廣度優先搜索和深度優先搜索128
6.4.1　有嚮圖的BFS和DFS129
6.4.2　無嚮圖的BFS134
6.4.3　無嚮圖更高效的BFS算法136
6.5　單源最短路徑139
6.5.1　競賽樹140
6.5.2　Dijkstra算法的I/O高效版本145
習題149
第7章　MapReduce算法概述150
7.1　MapReduce基礎150
7.1.1　MapReduce的基本模型151
7.1.2　mapper和reducer152
7.1.3　partitioner與combiner155
7.2　MapReduce算法設計方法157
7.2.1　局部聚閤158
7.2.2　兩種重要的算法設計模式——詞對法和條塊法163
7.2.3　二次排序168
7.2.4　MapReduce算法設計與算法實現技巧168
習題170
第8章　MapReduce算法例析171
8.1　連接算法171
8.1.1　普通連接算法171
8.1.2　相似連接算法184
8.2　圖算法192
8.2.1　基於廣度優先搜索的MapReduce圖處理算法193
8.2.2　PageRank的MapReduce算法197
8.2.3　最小生成樹的MapReduce算法200
8.2.4　使用圖算法的注意事項202
習題203
第9章　超越MapReduce的並行大數據處理204
9.1　基於迭代處理平颱的並行算法204
9.2　基於圖處理平颱的並行算法212
9.2.1　並行結點計算213
9.2.2　並行結點計算的平颱215
9.2.3　基於並行結點計算的單源最短路徑算法的設計與實現219
9.2.4　計算子圖同構221
習題223
第10章　眾包算法224
10.1　眾包的定義224
10.2　眾包的實例225
10.3　眾包的要素和關鍵技術228
10.3.1　眾包的流程228
10.3.2　眾包的報酬230
10.3.3　眾包中的關鍵技術230
10.4　眾包算法例析232
習題237
參考文獻238
· · · · · · (收起)