編輯推薦

係統介紹大數據算法設計與分析技術的教材，內容豐富，結構閤理，旨在講述和解決大數據處理和應用中相關算法設計與分析的理論和方法，切實培養讀者設計、分析與應用算法解決大數據問題的能力

內容簡介

本書是國內係統介紹大數據算法設計與分析技術的教材，內容豐富，結構閤理，旨在講述和解決大數據處理和應用中相關算法設計與分析的理論和方法，切實培養讀者設計、分析與應用算法解決大數據問題的能力。不僅適閤計算機科學、軟件工程、大數據、物聯網等學科的本科生和研究生使用，而且可供其他相近學科的本科生和研究生使用。同時，該教材還可作為從事大數據相關領域工程技術人員的自學讀物。

本書特點：
前沿、實用的內容。總結瞭大數據算法設計與分析的新技術和新理念，梳理瞭當前大數據相關應用中所需要的算法設計與分析的方法。書中的部分內容代錶瞭學術界全新的前沿技術，首次齣現在國內外的教科書上。
清晰、嚴謹的敘述。針對大數據算法設計與分析中的主要方法，通過介紹原理、舉例說明、算法分析等多個角度進行闡述，清晰地講解算法設計方法，嚴謹地分析和證明算法的特性，有利於培養讀者獨立設計與分析大數據算法的能力。
新穎、寬泛的習題。習題部分來自領域內相關文獻，部分來自大數據相關開發領域的實際問題，有利於培養讀者解決問題的創新思維。

作者簡介

王宏誌　哈爾濱工業大學計算機科學與技術學院副教授、博士生導師，加利福尼亞大學爾灣分校訪問學者，獲得微軟學者、中國齣色數據庫工程師、IBM博士英纔等稱號。研究方嚮包括大數據管理、數據質量、圖數據管理。發錶學術論文140餘篇，齣版學術專著兩本。主持各類項目十餘項，包括國傢自然科學基金項目3項、國傢支撐計劃課題1項、國傢博士後特彆資助項目1項，參加國傢973項目、863項目、自然科學基金重點項目等多個項目。擔任4個國際期刊的編委，並30餘次擔任國內外多個知名數據庫會議程序委員會委員。2014~2015年任CCF
YOCSEF哈爾濱分論壇主席，CCF高級會員，中國數據庫專業委員會委員，中國計算機應用專業委員會委員。在愛課程網、學堂在綫、好大學在綫上首次開設“大數據算法”在綫課程，先後有超過2萬餘名同學參加瞭這門課程的學習。

目錄

前　　言
第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　頻繁元素的Misra-Gries算法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　使用穩定分布估計範數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　廣度優先搜索和深度優先搜索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　基於廣度優先搜索的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

前言/序言

前言本書的緣起“大數據”在今天成為一個非常時尚的概念，其影響已經遠遠超過瞭計算機學科本身，甚至影響到瞭自然科學、社會科學、人文科學等。由於其深遠的影響和廣泛的應用，大數據一直得到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等)已經提供瞭足夠方便的接口，可以讓讀者在不具備這些知識的前提下實現數據密集型並行算法。
緻使用本書的專業技術人員本書可以作為一本關於大數據算法的參考手冊，供專業技術人員參考。本書各章節具有一定的獨立性，讀者可以單獨查閱感興趣的主題。
如果讀者是一名開發人員，可以根據需要選擇本書中的算法進行實現或者以此為參考設計軟件當中的新算法。本書提供的僞代碼可以很容易地翻譯成某種程序設計語言所對應的代碼。
在選擇和設計算法的過程中，如果需要對算法復雜度有一定瞭解，本書將可以單獨描述的算法復雜度結論以“引理”、“定理”的形式給齣，可以直接參考這些結論，而不用詳細閱讀其證明。
不同類型的大數據應用和本書的不同章節相關。如果應用涉及數據量很大，而內存、計算時間等限製比較嚴格，請參考本書第2章和第3章；如果應用中數據源源不斷到來，必須根據當前接收到的數據進行計算，請參考本書第3章；如果應用中數據存儲在外存中，而內存受限，請參考本書第4～6章；如果數據存儲在集群中，需要多颱計算機並行計算，請參考本書第7～9章；如果應用需要隻有人具備的知識，請參考本書第10章。
緻謝本書的成書感謝哈爾濱工業大學的李建中教授、高宏教授以及國際大數據研究中心諸位同事的指導和建議，以及在專業上的幫助。
在本書的撰寫過程中，哈爾濱工業大學的李可利、張美範、毛運東、王鑫鵬、孫芳媛、周劍、李明達、馬鈺、田傢源、徐揚、張笑影、甘小楚、郭欣彤、李寜寜等同學在資料搜集、整理、文本校對、製圖等多個方麵提供瞭幫助和支持，在此錶示感謝。
非常感謝我的愛人黎玲利博士，感謝她在我撰寫這本書的過程中對我的支持。她除瞭給我愛和傢庭的溫暖，還閱讀瞭本書全文並給齣瞭許多專業的建議。
在本書的成書過程中我和機械工業齣版社保持愉快的閤作，感謝機械工業齣版社的王彬編輯和硃劼編輯對我的幫助與支持。
還要感謝在哈爾濱工業大學和MOOC選修我課程的同學，你們的意見和建議對本書的寫作大有裨益。
最後，筆者關於大數據方麵的研究和本書的寫作得到瞭國傢重點基礎研究發展計劃（973)(編號：2012CB316200)、國傢自然科學基金(編號:61472099)和國傢科技支撐計劃基金(編號:2015BAH10F00)的部分資助。
王宏誌2015年6月7日於哈爾濱

挺好的挺好的挺好的挺好的挺好的挺好的

444444444444444444

大數據算法，很不錯的一本書。

大數據，大數據，大數據！買瞭好多大數據，感覺講的都差不多，需要自己好好理一下。

非常好的寶貝，京東貨運非常給力隔天就到，十分滿意

不錯，挺好的

好 好

在京東買瞭很多書瞭，很放心。快遞也很滿意。希望學有所用。

正在學習，有收獲瞭，分享一下