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

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