前言

本书的缘起

“大数据”在今天成为一个非常时尚的概念，其影响已经远远超过了计算机学科本身，甚至影响到了自然科学、社会科学、人文科学等。由于其深远的影响和广泛的应用，大数据一直得到IT从业人员的重视，他们对大数据相关理论、技术的学习有着强烈的需求。

“算法设计与分析”是计算机科学的重要主题，进行大数据计算，“算法设计与分析”是必不可少的步骤，可以说，算法设计是“大数据落地”的关键之一。然而，虽然在今天的书店里，关于大数据的书籍数不胜数，但真正从“算法设计与分析”角度关注大数据的书却很少。究其原因，当前“大数据算法”的知识体系还远不完备，因为“大数据”是计算机学科的增长点之一，“大数据算法”的内涵和外延也不断发生着变化，而且大数据上算法设计与分析得到的知识驳杂，难以梳理出一个明晰的知识体系。而大数据不同方面的从业人员，对“大数据算法”的理解也不尽相同。作者曾经调研过国内外和“大数据算法”相关的课程，其教学内容的差异非常大。

因而，笔者写了本书，作为一种勇敢的尝试，试图兼顾深度和广度来介绍“大数据算法”。其缘起有三。

其一，笔者从本科加入了李建中教授领导的哈尔滨工业大学数据库研究中心，留校工作到现在。随着“数据”在计算机学科扮演的角色日益重要，中心的名字经历了“数据库研究中心”到“知识与数据工程研究中心”到“海量数据计算研究中心”到“国际大数据研究中心”的变化，并且一直是围绕“数据”的计算开展研究。在中心良好的学术氛围下，笔者进行了十几年“数据”计算的研究，也一直在思考“数据为中心的计算到底需要何种特别的算法设计技术”这一问题，有一些不成熟的心得，希望与读者分享。

其二，机械工业出版社王彬编辑在2013年全国大数据会议上邀请笔者写一本和“大数据”、“算法”相关的书，促使笔者去思考和学习，试图梳理出一条“大数据算法”的脉络。

其三，在网易云课堂的孙志岗总监的鼓动下，笔者在2014年开设了自己的第一门MOOC课程“大数据算法”,2014年夏季学期笔者在哈尔滨工业大学作为全校选修课也开设了“大数据算法”这门课程，这督促着笔者不得不从教学内容到教学方法上去思考如何表述“大数据算法”。在教学过程中，很多学习这门课程的学生询问教材的事情，很遗憾，笔者只能提供一个参考文献列表，而无法推荐教材，这也促使笔者撰写这样一本书。

本书的特点

本书对大数据计算中涉及的算法设计与分析技术进行了介绍，针对大数据对算法的要求，主要涉及四个方面：亚线性算法、外存算法、并行算法和众包算法。书中给出了多个算法，并对其进行了分析，尽可能使本书适用于各个层次的读者。

书中每一章涉及一类大数据算法设计技术，算法主要用自然语言、伪代码和例子来描述，力图使本书介绍的算法易懂易用。由于为大数据设计算法，在“大数据”上进行实验的成本比较高，因此“算法分析”在“大数据算法”中扮演着更重要的角色，本书也在算法分析方面投入了相当的笔墨。有不同需求的读者可以着重阅读本书不同的部分。

由于“大数据”涉及的内容较广，本书围绕大数据的特点着重介绍大数据算法设计与分析的方法，和大数据分析、大数据系统、大数据编程等书籍具有互补性，可以相互参照进行阅读。

本书适合作为本科生和研究生“大数据”或者“大数据算法”课程的教材，也可以作为“算法设计与分析”等课程的补充教材或课外读物。同时，本书也适合大数据领域从业人员参考。

由于本书是一种新的尝试，涉及的内容非常宽且又是变化迅速，尽管笔者尽全力来写本书（其中的一部分内容甚至来自于2015年发表的文献），但是由于笔者水平有限，在本书内容的安排、表述、推导等方面的各种不当之处在所难免，敬请读者在阅读本书的过程中，不吝提出宝贵的建议，以改进本书。读者的任何意见和建议请发至邮箱wangzh@hit.edu.cn。

致使用本书的教师

本书涉及了多方面内容，对于教学而言，本书适用于多门课程的教学，并可以作为“数据结构”、“算法设计与分析”、“数据库系统原理”等课程的补充教材，教师可以从本书中选择适合教学的内容，例如，第5章适合作为“数据库系统原理”这门课“数据库索引”部分的补充教学内容，第4章适合作为“数据结构”这门课“排序”部分的补充教学内容。

针对不同层次的教学可以选择不同的内容。针对本科生或者职业培训的教学可以侧重于算法设计，着重讲授算法本身和算法的应用场景，而对算法分析可以略讲；针对研究生的教学可以在讲算法设计的同时利用更多的时间来讲授算法的分析和推导。

本书每章后包含一些习题，供学生巩固所学内容。

致使用本书的学生

希望本书为学生提供“大数据算法”方面的入门指导，我们尽量让描述通俗易懂，但是一些算法、数据结构或者分析本身比较复杂，有些算法分析远看略显“高冷”，请在阅读时不要畏惧，可以按照相关的证明过程和推理步骤仔细梳理证明的脉络。对于本书涉及的一些可能没有学过的知识，通过“补充知识”部分进行了介绍。

要阅读本书，希望读者有一些算法和程序设计方面的基础，“数据结构”和“算法设计与分析”是本书的先修课程，如果读者没有学过这方面的课程，可以通过阅读《算法导论（原书第3版）》如下章节自学相关知识：第1～12章、第15～17章、第18章、第22～24章。本书第2章和第3章涉及一些概率分析知识，如果不需要掌握概率分析的技术而仅读懂本书，本书提供的补充知识足以帮助你理解证明过程；如果希望系统掌握概率分析，可以先阅读一下《概率与计算》的第1～6章，奠定概率分析方面的基础，再阅读本书第2章和第3章中的证明。本书第7～9章涉及了并行算法，但并不需要读者具备并行体系结构和并行计算相关的知识，因为当前平台（如Hadoop等）已经提供了足够方便的接口，可以让读者在不具备这些知识的前提下实现数据密集型并行算法。

致使用本书的专业技术人员

本书可以作为一本关于大数据算法的参考手册，供专业技术人员参考。本书各章节具有一定的独立性，读者可以单独查阅感兴趣的主题。

如果读者是一名开发人员，可以根据需要选择本书中的算法进行实现或者以此为参考设计软件当中的新算法。本书提供的伪代码可以很容易地翻译成某种程序设计语言所对应的代码。

在选择和设计算法的过程中，如果需要对算法复杂度有一定了解，本书将可以单独描述的算法复杂度结论以“引理”、“定理”的形式给出，可以直接参考这些结论，而不用详细阅读其证明。

不同类型的大数据应用和本书的不同章节相关。如果应用涉及数据量很大，而内存、计算时间等限制比较严格，请参考本书第2章和第3章；如果应用中数据源源不断到来，必须根据当前接收到的数据进行计算，请参考本书第3章；如果应用中数据存储在外存中，而内存受限，请参考本书第4～6章；如果数据存储在集群中，需要多台计算机并行计算，请参考本书第7～9章；如果应用需要只有人具备的知识，请参考本书第10章。

致谢

本书的成书感谢哈尔滨工业大学的李建中教授、高宏教授以及国际大数据研究中心诸位同事的指导和建议，以及在专业上的帮助。

在本书的撰写过程中，哈尔滨工业大学的李可利、张美范、毛运东、王鑫鹏、孙芳媛、周剑、李明达、马钰、田家源、徐扬、张笑影、甘小楚、郭欣彤、李宁宁等同学在资料搜集、整理、文本校对、制图等多个方面提供了帮助和支持，在此表示感谢。

非常感谢我的爱人黎玲利博士，感谢她在我撰写这本书的过程中对我的支持。她除了给我爱和家庭的温暖，还阅读了本书全文并给出了许多专业的建议。

在本书的成书过程中我和机械工业出版社保持愉快的合作，感谢机械工业出版社的王彬编辑和朱劼编辑对我的帮助与支持。

还要感谢在哈尔滨工业大学和MOOC选修我课程的同学，你们的意见和建议对本书的写作大有裨益。

最后，笔者关于大数据方面的研究和本书的写作得到了国家重点基础研究发展计划（973）（编号：2012CB316200）、国家自然科学基金（编号：61472099）和国家科技支撑计划基金（编号：2015BAH10F00）的部分资助。

王宏志

2015年6月7日于哈尔滨