本書是通俗易懂的大數據算法教程。通篇采用師生對話的形式，旨在用通俗的語言、輕松的氣氛，幫助讀者理解大數據計算領域中的基礎算法和思想。本書由背景篇、理論篇、應用篇和實踐篇四部分組成。背景篇介紹大數據、算法、大數據算法等基本概念和背景；理論篇介紹解決大數據問題的亞線性算法、磁盤算法、並行算法、眾包算法的基本思想和理論知識；應用篇介紹與大數據問題息息相關的數據挖掘和推薦系統的相關知識；實踐篇從實際應用出發，引導讀者動手操作，幫助讀者通過實際程序和實驗驗證磁盤算法、並行算法和眾包算法。在講解每一個大數據問題之前，本書都會介紹大量的經典算法和基礎數據結構知識，不僅可以幫助學習過數據結構與算法、算法設計與分析等課程的同學復習，同時能夠讓入門的「小菜鳥」們，不會因為沒有學習過經典算法而對本書望而卻步，輕松地掌握大數據算法！博士畢業以來一直哈爾濱工業大學計算機學院任職，根據2012年教育部學科評估，該學科排名第4。王博士現任軟件與理論學科副教授，博士生導師。發表論文100余篇，出版學術專著《XML查詢處理》和英文專著《Innovative Techniques and Applications of Entity Resolution》，撰寫3篇專著章節，擁有3項軟件著作權，完成經典教材《算法導論(第三版)》最后5章的翻譯，其論文被SCI/EI檢索60余次，引用300余次，其中5篇論文發表於頂級國際會議上。獲得微軟學者(亞太地區40人獲獎)、中國優秀數據庫工程師(全國10人獲獎)、IBM博士英才(大中華區8人獲獎)等稱號，「海量數據計算的理論和技術」獲得黑龍江省自然科學獎1項，其博士論文「XML數據查詢處理技術的研究」獲得哈爾濱工業大學優秀博士論文和中國計算機學會優秀博士論文。其在2014年與慕課網開設《大數據算法》課程，這是國內首次公開開設與大數據算法相關的課程，迄今已經有超過2萬人選課。其2008年在國際頂級會議VLDB上發表的論文是2000年以來第一篇國內學者獨立完成的VLDB論文，在國內外產生了較大影響。2011年在微軟亞洲研究院期間提出的海量圖數據的匹配算法國際上首次將子圖匹配算法擴展到了在規模為10億級別的圖上，該算法於2012年發表以來已被引用超過30次，並已經進入微軟亞洲研究院的Trinity系統。王博士在國內外多個知名數據庫會議擔任程序委員會委員20余次，在國際學術領域有一定影響。王博士在大數據管理、Web數據管理、數據質量管理、圖數據管理的研究和開發方面都有用豐富的經驗。

第1篇 背景篇第1章 何謂大數據41.1 身邊的大數據41.2 大數據的特點和應用6第2章 何謂算法82.1 算法的定義82.2 算法的分析142.3 基礎數據結構——線性表242.4 遞歸——以階乘為例28第3章 何謂大數據算法31第2篇 理論篇第4章 窺一斑而見全豹——亞線性算法344.1 亞線性算法的定義344.2 空間亞線性算法354.2.1 水庫抽樣354.2.2 數據流中的頻繁元素374.3 時間亞線性計算算法404.3.1 圖論基礎回顧404.3.2 平面圖直徑454.3.3 最小生成樹464.4 時間亞線性判定算法534.4.1 全0數組的判定534.4.2 數組有序的判定55第5章 價錢與性能的平衡——磁盤算法585.1 磁盤算法概述585.2 外排序625.3 外存數據結構——磁盤查找樹715.3.1 二叉搜索樹回顧715.3.2 外存數據結構——B樹785.3.3 高維外存查找結構——KD樹805.4 表排序835.5 表排序的應用865.5.1 歐拉回路技術865.5.2 父子關系判定875.5.3 前序計數885.6 時間前向處理技術905.7 縮圖法98第6章 1+1＞2——並行算法1036.1 MapReduce初探1036.2 MapReduce算法實例1066.2.1 字數統計1066.2.2 平均數計算1086.2.3 單詞共現矩陣計算1116.3 MapReduce進階算法1156.3.1 join操作1156.3.2 MapReduce圖算法概述1226.3.3 基於路徑的圖算法125第7章 超越MapReduce的並行計算1317.1 MapReduce平台的局限1317.2 基於圖處理平台的並行算法1367.2.1 概述1367.2.2 BSP模型下的單源最短路徑1377.2.3 計算子圖同構141第8章 眾人拾柴火焰高——眾包算法1448.1 眾包概述1448.1.1 眾包的定義1448.1.2 眾包應用舉例1468.1.3 眾包的特點1498.2 眾包算法例析152第3篇 應用篇第9章 大數據中有黃金——數據挖掘1589.1 數據挖掘概述1589.2 數據挖掘的分類1599.3 聚類算法——k—means1609.4 分類算法——Naive Bayes166第10章 推薦系統17010.1 推薦系統概述17010.2 基於內容的推薦方法17310.3 協同過濾模型176第4篇 實踐篇第11章 磁盤算法實踐186第12章 並行算法實踐19412.1 Hadoop MapReduce實踐19412.1.1 環境搭建19412.1.2 配置Hadoop20112.1.3 「Hello World」程序——WordCount20312.1.4 Hadoop實踐案例——記錄去重21312.1.5 Hadoop實踐案例——等值連接21612.1.6 多機配置22112.2 適於迭代並行計算的平台——Spark22412.2.1 Spark初探22412.2.2 單詞出現行計數23012.2.3 在Spark上實現WordCount23612.2.4 在HDFS上使用Spark24112.2.5 Spark的核心操作——Transformation和Action24412.2.6 Spark實踐案例——PageRank247第13章 眾包算法實踐25113.1 認識AMT25113.2 成為眾包工人252

這是一個互聯網的時代，也是一個大數據的時代。經常有朋友問起：什麼是大數據？大數據是做什麼用的？我們為什麼要研究大數據？應該怎麼研究大數據？在尋找這些問題的答案時，許多朋友找到的內容常常是專業的概念、復雜的公式和難懂的「算法」，這讓他們望而卻步。很多計算機專業的新生或低年級學生在聽到大數據的概念后對其非常好奇，卻因沒有足夠扎實的專業基礎知識而無法認識和理解大數據問題，更無法對大數據問題給出很好的解決辦法。於是，筆者決定編寫一本新生乃至非專業人士也能讀懂的大數據算法教程。