720
《大數據算法》一導讀
前 言
本書的緣起
“大數據”在今天成為一個非常時尚的概念，其影響已經遠遠超過了計算機學科本身，甚至影響到了自然科學、社會科學、人文科學等。由於其深遠的影響和廣泛的應用，大數據一直得到IT從業人員的重視，他們對大數據相關理論、技術的學習有著強烈的需求。
“算法設計與分析”是計算機科學的重要主題，進行大數據計算，“算法設計與分析”是必不可少的步驟，可以說，算法設計是“大數據落地”的關鍵之一。然而，雖然在今天的書店裏，關於大數據的書籍數不勝數，但真正從“算法設計與分析”角度關注大數據的書卻很少。究其原因，當前“大數據算法”的知識體係還遠不完備，因為“大數據”是計算機學科的增長點之一，“大數據算法”的內涵和外延也不斷發生著變化，而且大數據上算法設計與分析得到的知識駁雜，難以梳理出一個明晰的知識體係。而大數據不同方麵的從業人員，對“大數據算法”的理解也不盡相同。作者曾經調研過國內外和“大數據算法”相關的課程，其教學內容的差異非常大。
因而，筆者寫了本書，作為一種勇敢的嚐試，試圖兼顧深度和廣度來介紹“大數據算法”。其緣起有三。
其一，筆者從本科加入了李建中教授領導的哈爾濱工業大學數據庫研究中心，留校工作到現在。隨著“數據”在計算機學科扮演的角色日益重要，中心的名字經曆了“數據庫研究中心”到“知識與數據工程研究中心”到“海量數據計算研究中心”到“國際大數據研究中心”的變化，並且一直是圍繞“數據”的計算開展研究。在中心良好的學術氛圍下，筆者進行了十幾年“數據”計算的研究，也一直在思考“數據為中心的計算到底需要何種特別的算法設計技術”這一問題，有一些不成熟的心得，希望與讀者分享。
其二，機械工業出版社王彬編輯在2013年全國大數據會議上邀請筆者寫一本和“大數據”、“算法”相關的書，促使筆者去思考和學習，試圖梳理出一條“大數據算法”的脈絡。
其三，在網易雲課堂的孫誌崗總監的鼓動下，筆者在2014年開設了自己的第一門MOOC課程“大數據算法”，2014年夏季學期筆者在哈爾濱工業大學作為全校選修課也開設了“大數據算法”這門課程，這督促著筆者不得不從教學內容到教學方法上去思考如何表述“大數據算法”。在教學過程中，很多學習這門課程的學生詢問教材的事情，很遺憾，筆者隻能提供一個參考文獻列表，而無法推薦教材，這也促使筆者撰寫這樣一本書。
本書的特點
本書對大數據計算中涉及的算法設計與分析技術進行了介紹，針對大數據對算法的要求，主要涉及四個方麵：亞線性算法、外存算法、並行算法和眾包算法。書中給出了多個算法，並對其進行了分析，盡可能使本書適用於各個層次的讀者。
書中每一章涉及一類大數據算法設計技術，算法主要用自然語言、偽代碼和例子來描述，力圖使本書介紹的算法易懂易用。由於為大數據設計算法，在“大數據”上進行實驗的成本比較高，因此“算法分析”在“大數據算法”中扮演著更重要的角色，本書也在算法分析方麵投入了相當的筆墨。有不同需求的讀者可以著重閱讀本書不同的部分。
由於“大數據”涉及的內容較廣，本書圍繞大數據的特點著重介紹大數據算法設計與分析的方法，和大數據分析、大數據係統、大數據編程等書籍具有互補性，可以相互參照進行閱讀。
本書適合作為本科生和研究生“大數據”或者“大數據算法”課程的教材，也可以作為“算法設計與分析”等課程的補充教材或課外讀物。同時，本書也適合大數據領域從業人員參考。
由於本書是一種新的嚐試，涉及的內容非常寬且又是變化迅速，盡管筆者盡全力來寫本書(其中的一部分內容甚至來自於2015年發表的文獻)，但是由於筆者水平有限，在本書內容的安排、表述、推導等方麵的各種不當之處在所難免，敬請讀者在閱讀本書的過程中，不吝提出寶貴的建議，以改進本書。讀者的任何意見和建議請發至郵箱wangzh@hit.edu.cn。
致使用本書的教師
本書涉及了多方麵內容，對於教學而言，本書適用於多門課程的教學，並可以作為“數據結構”、“算法設計與分析”、“數據庫係統原理”等課程的補充教材，教師可以從本書中選擇適合教學的內容，例如，第5章適合作為“數據庫係統原理”這門課“數據庫索引”部分的補充教學內容，第4章適合作為“數據結構”這門課“排序”部分的補充教學內容。
針對不同層次的教學可以選擇不同的內容。針對本科生或者職業培訓的教學可以側重於算法設計，著重講授算法本身和算法的應用場景，而對算法分析可以略講；針對研究生的教學可以在講算法設計的同時利用更多的時間來講授算法的分析和推導。
本書每章後包含一些習題，供學生鞏固所學內容。
致使用本書的學生
希望本書為學生提供“大數據算法”方麵的入門指導，我們盡量讓描述通俗易懂，但是一些算法、數據結構或者分析本身比較複雜，有些算法分析遠看略顯“高冷”，請在閱讀時不要畏懼，可以按照相關的證明過程和推理步驟仔細梳理證明的脈絡。對於本書涉及的一些可能沒有學過的知識，通過“補充知識”部分進行了介紹。
要閱讀本書，希望讀者有一些算法和程序設計方麵的基礎，“數據結構”和“算法設計與分析”是本書的先修課程，如果讀者沒有學過這方麵的課程，可以通過閱讀《算法導論(原書第3版)》 該書由機械工業出版社出版，ISBN:978-7-111-40701-1。——編輯注如下章節自學相關知識：第1～12章、第15～17章、第18章、第22～24章。本書第2章和第3章涉及一些概率分析知識，如果不需要掌握概率分析的技術而僅讀懂本書，本書提供的補充知識足以幫助你理解證明過程；如果希望係統掌握概率分析，可以先閱讀一下《概率與計算》 該書由機械工業出版社出版，ISBN:978-7-111-20805-1。——編輯注的第1～6章，奠定概率分析方麵的基礎，再閱讀本書第2章和第3章中的證明。本書第7～9章涉及了並行算法，但並不需要讀者具備並行體係結構和並行計算相關的知識，因為當前平台(如Hadoop等)已經提供了足夠方便的接口，可以讓讀者在不具備這些知識的前提下實現數據密集型並行算法。
目 錄
第1章 緒論
1.1 大數據概述
1.2 大數據算法
1.3 大數據算法設計與分析
1.4 本書的內容
第2章 時間亞線性算法
2.1 時間亞線性算法概述
2.2 最小生成樹代價估計
2.3 時間亞線性判定算法概述
2.4 數組有序的判定算法
2.5 串相等判定算法
第3章 空間亞線性算法
3.1 空間亞線性算法概述
3.2 水庫抽樣
3.3 尋找頻繁元素的非隨機算法
3.4 估算不同元素的數量
3.5 尋找頻繁元素的隨機算法
第4章 外存算法概述
4.1 外存存儲結構與外存算法概述
4.2 外存算法示例：外存排序算法
4.2.1 外存歸並排序算法
4.2.2 外存多路快速排序算法
4.2.3 外存計算的下界
4.3 外存數據結構示例：外存搜索樹
習題
第5章 外存查找結構
5.1 B樹
5.2 加權平衡B樹
5.3 持久B樹
5.4 緩存樹
5.5 KDB樹
5.6 O樹
習題
第6章 外存圖數據算法
6.1 線性表排名及其應用
6.1.1 線性表排名問題
6.1.2 歐拉回路
6.1.3 父子關係判定
6.1.4 前序計數
6.1.5 計算子樹大小
6.2 時間前向處理方法
6.2.1 DAG形式邏輯表達式計算問題
6.2.2 最大獨立集合算法
6.3 縮圖法
6.3.1 基於縮圖法的圖連通分量計算半外存算法
6.3.2 基於縮圖法的圖連通分量計算全外存算法
6.3.3 最小生成樹算法
6.4 廣度優先搜索和深度優先搜索
6.4.1 有向圖的BFS和DFS
6.4.2 無向圖的BFS
6.4.3 無向圖更高效的BFS算法
6.5 單源最短路徑
6.5.1 競賽樹
6.5.2 Dijkstra算法的I/O高效版本
習題
第7章 MapReduce算法概述
7.1 MapReduce基礎
7.1.1 MapReduce的基本模型
7.1.2 mapper和reducer
7.1.3 partitioner與combiner
7.2 MapReduce算法設計方法
7.2.1 局部聚合
7.2.2 兩種重要的算法設計模式——詞對法和條塊法
7.2.3 二次排序
7.2.4 MapReduce算法設計與算法實現技巧
習題
第8章 MapReduce算法例析
8.1 連接算法
8.1.1 普通連接算法
8.1.2 相似連接算法
8.2 圖算法
8.2.1 基於廣度優先搜索的MapReduce圖處理算法
8.2.2 PageRank的MapReduce算法
8.2.3 最小生成樹的MapReduce算法
8.2.4 使用圖算法的注意事項
習題
第9章 超越MapReduce的並行大數據處理
9.1 基於迭代處理平台的並行算法
9.2 基於圖處理平台的並行算法
9.2.1 並行結點計算
9.2.2 並行結點計算的平台
9.2.3 基於並行結點計算的單源最短路徑算法的設計與實現
9.2.4 計算子圖同構
習題
第10章 眾包算法
10.1 眾包的定義
10.2 眾包的實例
10.3 眾包的要素和關鍵技術
10.3.1 眾包的流程
10.3.2 眾包的報酬
10.3.3 眾包中的關鍵技術
10.4 眾包算法例析
最後更新：2017-06-21 14:32:00