大數據算法

目錄
前  言
第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 頻繁元素的MisraGries算法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 使用穩(wěn)定分布估計范數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 廣度優(yōu)先搜索和深度優(yōu)先搜索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 基于廣度優(yōu)先搜索的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