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

目錄
前  言
第1章 緒論1
 1.1 大數(shù)據(jù)概述1
 1.1.1 什么是大數(shù)據(jù)1
 1.1.2 無處不在的大數(shù)據(jù)1
 1.1.3 大數(shù)據(jù)的特點3
 1.1.4 大數(shù)據(jù)的應用4
 1.2 大數(shù)據(jù)算法5
 1.2.1 大數(shù)據(jù)上求解問題的過程6
 1.2.2 大數(shù)據(jù)算法的定義7
 1.2.3 大數(shù)據(jù)的特點與大數(shù)據(jù)算法9
 1.2.4 大數(shù)據(jù)算法的難度9
 1.2.5 大數(shù)據(jù)算法的應用10
 1.3 大數(shù)據(jù)算法設計與分析11
 1.3.1 大數(shù)據(jù)算法設計技術(shù)11
 1.3.2 大數(shù)據(jù)算法分析技術(shù)12
 1.4 本書的內(nèi)容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 連通分量個數(shù)估計算法18
 2.2.2 最小生成樹代價估計算法20
 2.3 時間亞線性判定算法概述23
 2.4 數(shù)組有序的判定算法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 估算不同元素的數(shù)量35
 3.4.1 基本算法35
 3.4.2 改進算法38
 3.5 尋找頻繁元素的隨機算法42
 3.5.1 略圖法42
 3.5.2 計數(shù)最小略圖45
 3.6 估計頻率矩47
 3.6.1 頻率矩的AMS估計算法47
 3.6.2 基于拔河略圖的頻率矩估計51
 3.6.3 使用穩(wěn)定分布估計范數(shù)53
 習題57
第4章 外存算法概述60
 4.1 外存存儲結(jié)構(gòu)與外存算法概述60
 4.2 外存算法示例：外存排序算法64
 4.2.1 外存歸并排序算法64
 4.2.2 外存多路快速排序算法68
 4.2.3 外存計算的下界74
 4.3 外存數(shù)據(jù)結(jié)構(gòu)示例：外存搜索樹77
 習題78
第5章 外存查找結(jié)構(gòu)80
 5.1 B樹80
 5.2 加權(quán)平衡B樹87
 5.3 持久B樹90
 5.4 緩存樹94
 5.5 KDB樹98
 5.6 O樹103
 習題107
第6章 外存圖數(shù)據(jù)算法109
 6.1 線性表排名及其應用109
 6.1.1 線性表排名問題109
 6.1.2 歐拉回路114
 6.1.3 父子關(guān)系判定115
 6.1.4 前序計數(shù)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算法設計與算法實現(xiàn)技巧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的并行大數(shù)據(jù)處理204
 9.1 基于迭代處理平臺的并行算法204
 9.2 基于圖處理平臺的并行算法212
 9.2.1 并行結(jié)點計算213
 9.2.2 并行結(jié)點計算的平臺215
 9.2.3 基于并行結(jié)點計算的單源最短路徑算法的設計與實現(xiàn)219
 9.2.4 計算子圖同構(gòu)221
 習題223
第10章 眾包算法224
 10.1 眾包的定義224
 10.2 眾包的實例225
 10.3 眾包的要素和關(guān)鍵技術(shù)228
 10.3.1 眾包的流程228
 10.3.2 眾包的報酬230
 10.3.3 眾包中的關(guān)鍵技術(shù)230
 10.4 眾包算法例析232
 習題237
參考文獻238