第1章 绪论

1.1 大数据概述

毫无疑问，大数据已经成为一个热门的概念，然而，不同领域（例如商业、系统结构、数据管理等）对这个概念的解读却各不相同。本节我们对大数据的定义、特点和应用进行概述。

1.1.1 什么是大数据

“大数据”的概念起源于2008年9月《自然》（Nature）杂志刊登的名为“Big Data”的专题，继而迅速得到了科学、计算机、经济等不同领域专家的响应。由于其成因复杂，对大数据目前没有公认的定义，不同的研究人员从不同领域对大数据进行了定义，下面列出三个不同角度对大数据的定义。

1）Kusnetzky Dan在What is“Big Data? ”一文中提出，大数据是指所涉及的数据量规模巨大，无法通过人工在合理时间内截取、管理、处理并整理成为人类所能解读的信息。

2）维克托·迈尔-舍恩伯格、肯尼斯·库克耶在《大数据时代》一书中把大数据看成一种方法，即不用随机分析法（抽样调查）这样的捷径，而采用所有数据的方法。

3）“大数据”研究机构Gartner的报告指出，“大数据”是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

这三种定义中，第一种定义更强调处理能力，第二种定义更强调应用方法，第三种定义更侧重应用价值。本书的主题是“大数据算法”，因而更加侧重于第一种定义，即“规模巨大，无法通过人工来处理”。

1.1.2 无处不在的大数据

现实生活中的数据有多大呢？根据统计，在2006年，个人用户刚刚迈进TB时代，这一年全球共产生了约180EB=180×1018字节的数据；在2011年，达到了1.8ZB=1.8×1021字节。有市场研究机构预测：到2020年，整个世界的数据总量将会增长44倍。你也许会好奇为何会产生如此庞大的数据，下面我们举几个现实中的大数据例子。

·社交网络 由于数据来自所有用户的参与，社交网络中的数据量非常大，而且增长非常迅速。例如，新浪微博在晚高峰的时候1秒产生的数据达到100条以上。如果把脸书（Facebook）中的社交网络看成图，在2012年这个图已经达到了超过8亿个顶点，平均每个点的度超过130，每天增加的数据量达到500TB。

·科学仪器 科学仪器获取了非常巨大的数据，比如说中国遥感国家重点实验室采集的中国大陆地表信息，每个月产生4TB数据。中国天文观测站用LAMOST每年观测到的数据达到3.65TB，美国NASA中心每年获取超过125TB的数据，英国Sanger中心2002年就已经收集了20TB的数据，并且以每年4倍的速度增长。

·移动通信 我们每天使用的手机产生了非常巨大的数据，中国移动每年产生的记录超过300TB。

·传感数据 传感器持续检测环境信息并不断返回结果，产生了巨大的数据。以波音787为例，其每一个飞行来回可产生TB级的数据，美国每个月收集360万次飞行记录；监视所有飞机中的25000个引擎，每个引擎一天产生588GB的数据。风力发电机装有测量风速、螺距、油温等多种传感器，每隔几毫秒测一次，用于检测叶片、变速箱、变频器等的磨损程度，一个具有500个风机的风场一年会产生2PB的数据。

·医疗数据 美国著名医疗保健公司InSiteOne平均每年获取2.1PB的放射影像数据，英国每年产生300TB乳腺癌数据，在美国相应的数据量达到2.6PB。哈尔滨医科大学第一附属医院每年通过各类医疗仪器搜集的数据超过30TB。

·商务数据 生活中的每次刷卡，在超市或者网络中购买的每件商品都产生相应的数据。淘宝网站每天有超过数千万笔交易，单日数据产生量超过50TB。为了有效使用商务大数据，沃尔玛建立了包含PB级数据的数据仓库，Bestbuy建立了包含TB级数据的数据仓库。

1.1.3 大数据的特点

通常用3V或者4V来描述大数据的特点，本小节用4V描述大数据的特点。

1．规模性（Volume，耗费大量存储、计算资源）

大数据之“大”，体现在数据的存储和计算均需耗费海量规模的资源上：美国宇航局收集和处理的气候观察、模拟数据达到32PB；谷歌公司索引的网页总数超过1万亿；FICO的信用卡欺诈检测系统保护全世界超过18亿个活跃信用卡账户。

2．高速性（Velocity，增长迅速、急需实时处理）

大数据的另一特点在于速度快：大型强子对撞机实验设备中包含了15亿个传感器，平均每秒收集超过4亿条实验数据；每秒超过3万次用户查询提交到谷歌，3万条微博被新浪用户撰写。而在感知、传输、决策、控制这一闭环控制过程中的计算，对数据实时处理有着极高的要求，通过传统数据库查询方式得到的“当前结果”很可能已经没有价值，只有最新的数据才有价值。

3．多样性（Variety，来源广泛、形式多样）

在大数据背景下，数据在来源和形式上的多样性愈加凸显：除大量以非结构化形式存在的文本数据，也存在位置、图片、音频、视频等信息。除信息形式的多元化，信息的来源也表现出多样性：从网络日志、物联网、移动设备、传感器到基因图谱、医疗影像、天体运行轨迹、交通物流数据等。大数据中的多样性已经超越了数据管理中的异构数据库，其不仅仅是模式或模型的不一样，甚至数据本身的存在形式也完全不同，比如说存在文本、多媒体数据，也存在仪器采集来的完全是数字的数据，以及用户产生的用户行为的数据，这些数据有各种各样的存在形式，这些形式导致处理技术的差异，因此需要新的处理技术。

4．价值稀疏性（Value，价值总量大、知识密度低）

大数据以其高价值吸引了广泛关注。据全球著名咨询公司麦肯锡报告：“如果能够有效地利用大数据来提高效率和质量，预计美国医疗行业每年通过数据获得的潜在价值可超过3000亿美元，能够使美国医疗卫生支出降低8%。”虽然大数据价值高，但是知识密度非常低。谷歌公司首席经济学家Hal Varian指出“数据是广泛可用的，所缺乏的是从中提取出知识的能力”; IBM副总裁兼CTO Dietrich表示“可以利用Twitter数据获得用户对某个产品的评价，但是往往上百万条记录中只有很小的一部分真正讨论这款产品”。

只有经过高度分析的大数据才可以产生新的价值，需要设计能够适应上述特征的大数据处理算法来处理数据。

1.1.4 大数据的应用

大数据在许多方面有着广泛的应用，甚至说达到了无处不在的程度，本小节将讨论若干大数据的典型应用。

1．预测

2013年2月19日，微软研究院的David Rothschil博士带领的大数据分析团队通过分析入围影片相关数据，预测出2013年各项奥斯卡大奖的最终归属，成功命中除最佳导演奖（华裔导演李安获得）外的13项大奖。

《纽约时报》FiveThirtyEight的博客作者和统计学家Nate Silver预测：奥巴马有超过80%的机会赢得周二的大选（后来提升到90.9%）; David Rothschild带领的分析团队，在2012年使用一个通用的数据驱动型模型，预测了美国50个州和哥伦比亚特区共计51个选区中50个地区的选举结果，准确率高于98%。

日本国内有一个网站，你只要打开这个网站用自己的Twitter账号登录，就可以在短时间内通过数万条Twitter找出可能感冒的人，并对过去的感冒情况和今日的感冒情况进行分析（以及统计目前发烧以及嗓子痛的患者数量）。另外该程序还会结合气温和湿度的变化来预测将来感冒的流行情况，并开发了一个“易感冒日历”。通过这个服务，人们就能知道身边有多少人有感冒的症状，并提前做好预防。

2．推荐

商务信息推荐和我们每天的生活息息相关，用户在淘宝、京东、卓越等电子商务网站上购物的时候，网站会为我们推荐相关的商品，这些推荐来自大数据。商家采集了大量的用户行为信息，包括购买、浏览、评价等，根据这些行为信息预测当前使用这个网站的用户下一步可能有哪些行为，再根据预测的结果来给用户推荐他最需要的商品，从而提高用户的购买效率。推荐是很多网站的重要盈利模式，借助推荐技术，大数据能够为电子商务带来价值。

3．商业情报分析

为了对营销情况进行有效分析，沃尔玛建立了PB级的数据仓库，使得在线完成购物率提高了10%到15%。连锁超市特易购（Tesco PLC）在数据仓库中搜集了700多万个冰箱的数据，通过对这些数据的分析，能够全面监控冰箱状况，并且根据监控和预测的结果，对这些冰箱进行主动维修，从而降低能耗。还有一些案例，比如说有一家牛排店，通过分析Twitter大数据知道哪些人可能是常客，根据客户以往的订单，推测出其所乘的航班，然后派出一位身着燕尾服的侍者为客户提供晚餐，通过这样的服务吸引了越来越多的熟客。

4．科学研究

今天的科学研究已经超越了牛顿的时代。从历史上看，第谷积攒了大量的天文数据，开普勒通过数据的分析得到了天体三大运动定律，当时计算靠手工进行，需要人工分析，缺少计算机这样有效的计算工具，如果当年有大数据的处理方法的话，开普勒三大运动定律可能更早出来。今天大量的科学仪器产生了海量的数据，这样的数据量已经不是人拿纸拿笔就能分析的，而是需要强大的数据处理能力。今天，由于大数据的支持，科学研究由假设驱动转向基于探索的科学方法，过去设问“我应该设计什么样的实验来验证这个假设？”，现在设问“从这些数据中我能够看到什么？”和“如果把其他领域的数据融合进来，能够发现什么？”，数据密集型科学发现被称为“科学研究的第四范式”。以美国能源部为例，其提出了基于大数据科学研究的支持计划，包括生物和环境的研究计划、大气辐射测量气候的研究计划以及系统生物学的知识库对微生物和植物环境这些功能群落的识别。

1.2 大数据算法

这一节我们概述大数据算法。

1.2.1 大数据上求解问题的过程

首先我们看一看在大数据上问题求解的过程。我们面对的是一个计算问题，也就是说我们要用计算机来处理一个问题。

拿到一个计算问题之后，首先需要判定这个问题是否可以用计算机进行计算，如果学习过可计算性理论，就可以了解有许多问题计算机是无法计算的，比如判断一个程序是否有死循环，或者是否存在能够杀所有病毒的软件，这些问题都是计算机解决不了的。从“可计算”的角度来看，大数据上的判定问题和普通的判定问题是一样的，也就是说，如果还是用我们今天的电子计算机模型，即图灵机模型，在小数据上不可计算的问题，在大数据上肯定也不可计算。计算模型的计算能力是一样的，只不过是算得快慢的问题。

那么，大数据上的计算问题与传统的计算问题有什么本质区别呢？

第一个不同之处是数据量，就是说处理的数据量要比传统的数据量大。第二个不同之处是有资源约束，就是说数据量可能很大，但是能真正用来处理数据的资源是有限的，这个资源包括CPU、内存、磁盘、计算所消耗的能量。第三个不同之处是对计算时间存在约束，大数据有很强的实时性，最简单的一个例子是基于无线传感网的森林防火，如果能在几秒之内自动发现有火情发生，这个信息是非常有价值的，如果三天之后才发现火情，树都烧完了，这个信息就没有价值，所以说大数据上的计算问题需要有一个时间约束，即到底需要多长时间得到计算结果才是有价值的。判定能否在给定数据量的数据上，在计算资源存在约束的条件下，在时间约束内完成计算任务，是大数据上计算的可行性问题，需要计算复杂性理论来解决，然而，当前面向大数据上的计算复杂性理论研究还刚刚开始，有大量的问题需要解决。

注意：在本书中，有的算法可能很简单，寥寥几行就结束了，然而后面的分析却长达几页。这本书花更大的精力讲授算法分析，是因为在大数据上进行算法设计的时候，要先分析清楚这个算法是否适用于大数据的情况，然后才能使用。

本书讨论的主要内容是大数据上算法的设计与分析，即设计大数据上的算法并且加以分析。

特别值得说明的一点是，对于大数据上的算法，算法分析显得尤为重要，这是为什么呢？对于小数据上的算法可以通过实验的方法来测试性能，实验可以很快得到结果，但是在大数据上，实验就不是那么简单了，经常需要成千上万的机器才能够得出结果。为了避免耗费如此高的计算成本，大数据上的算法分析就十分重要了。

经过算法设计与分析，得到了算法。接着需要用计算机语言来实现算法，得到的是一些程序模块，下一步用这些程序模块构建软件系统。这些软件系统需要相应的平台来实现，比如常说的Hadoop、SparK都是实现软件系统的平台。

上面的叙述可以归纳为图1-1，从中可以看到，大数据算法与分析在整个大数据问题求解过程中扮演着一个核心的角色，因而本书将对此重点介绍。

1.2.2 大数据算法的定义

1．大数据算法是什么

根据大数据上的计算过程可以定义大数据算法的概念，如定义1-1所示。

定义1-1（大数据算法） 在给定的资源约束下，以大数据为输入，在给定时间约束内可以计算出给定问题结果的算法。

这个定义和传统的算法有一样的地方，首先大数据算法也是一个算法，有输入有输出；而且算法必须是可行的，也必须是机械执行的计算步骤。

第一个不同之处是，大数据算法是有资源约束的，这意味着资源不是无限的，可能在100KB数据上可行的算法在100MB的数据上不可行，最常见的一个错误是内存溢出。这意味着进行大数据处理的内存资源不足，因此在大数据算法的设计过程中，资源是一个必须考虑的约束。第二个不同之处是，大数据算法以大数据为输入，而不是以传统数据的小规模为输入。第三个不同之处是，大数据算法需要在时间约束之内产生结果，因为有些情况下过了时间约束大数据会失效，有些情况下超过时间约束的计算结果没有价值。

2．大数据算法可以不是什么

有了大数据作为输入和运行时间作为约束，大数据算法和传统算法就有了明确的区别。

第一，大数据算法可以不是精确算法。因为有些情况下，能够证明对于给定的数据输入规模和资源约束，确实不可能得到精确解。

第二，大数据算法可以不是内存算法。由于数据量很大，在很多情况下，把所有数据都放在内存中几乎不可能，因为对于现在的PC来说，内存的规模在GB级，对于高档一些的并行机和服务器来说内存也就是TB级，这个规模对于许多应用中的数据量是远远不够的，必须使用外存甚至于网络存储。因此，大数据算法可以不仅仅在内存中运行。

第三，大数据算法可以不是串行算法。有的时候，单独一台计算机难以处理大规模数据，需要多台机器协同并行计算，即并行算法。一个典型的例子是Google公司中的计算，为了支持搜索引擎，Google公司需要处理大规模来自互联网的数据，因而大数据里面的很多重要概念是Google提出的，例如并行平台MapReduce。Google公司的数据规模太大，再好的机器也无法独自处理，需要用成千上万台机器构成一个机群来并行处理。

第四，大数据算法可以不是仅在电子计算机上运行的算法。有时对于某些任务而言，让计算机处理很复杂，而让人做很简单。对于这些问题，可以让人和计算机一起来做，因此就有了人和计算机协同的算法。

而传统算法分析与设计课程中的算法，主要是内存算法、精确算法、串行算法且完全在电子计算机上执行，这和本书中的大数据算法不同。

3．大数据算法不仅仅是什么

下面从大数据概念出发，澄清一些大数据算法的片面观点。

第一，大数据算法不仅仅是基于MapReduce的算法。讲到大数据算法，可能有很多人就会想到MapReduce, MapReduce上的算法确实在很多情况下适用于大数据，而且更确切说MapReduce上的算法是一类很重要的大数据算法，但是大数据算法不仅是MapReduce上的算法。

第二，大数据算法不仅仅是云计算平台上的算法。说到大数据算法，很多人可能会想到云计算，云上的算法是不是大数据算法呢？云上的算法不全是大数据算法，有的算法不是面向大数据的，例如安全性相关的算法和计算密集型算法，而且大数据算法也不都是云上的算法，大数据算法有的可以是单机的，甚至可以是手机或者传感器这种计算能力很差的设备。

第三，大数据算法不仅仅是数据分析与挖掘中的算法。分析与挖掘是大数据中比较热的概念，也确实是大数据的重要方面。之所以用得比较多，是因为其商业价值比较明显。然而，大数据的应用除了需要分析与挖掘，还有获取、清洗、查询处理、可视化等方面，这些都需要大数据算法的支持。

第四，大数据算法不仅仅是数据库中的算法。提到大数据，自然会联想到这是和数据管理密切相关的。大数据算法是否等同于数据库中的算法呢？不完全是这样，虽然数据库中的算法是大数据算法的一个重要组成部分，今天进行大数据算法研究的多是数据库和数据管理研究领域的专家，但是不全是数据库领域的。当前研究大数据算法的专家，有的研究背景是数学理论和算法理论，还有的来自机器学习和各种大数据应用的研究领域。因此大数据算法不仅仅是数据库中的算法，还有专门为大数据设计的算法。

1.2.3 大数据的特点与大数据算法

大数据的特点决定了大数据算法的设计方法。正如前面所介绍的，大数据的特点通常用四个V来描述。这四个V里面和大数据算法密切相关的，有两个V。一个是数据量（Volume）大，也就是大数据算法必须处理足够大的数据量。另一个是速度（Velocity），速度有两方面：①大数据的更新速度很快，相应的大数据算法也必须考虑更新算法的速度；②要求算法具有实时性，因此大数据算法要考虑到运算时间。对于另外两个V，我们假设大数据算法处理的数据已经是经过预处理的，其多样性（Variety）已经被屏蔽掉了。关于价值（Value）本书也不考虑，而假设数据或算法的价值是预先知道的。

1.2.4 大数据算法的难度

要设计一个大数据算法并不容易，因为大数据具有规模大、速度快的特点。大数据算法设计的难度主要体现在四个方面。

1．访问全部数据时间过长

有的时候算法访问全部数据时间太长，应用无法接受。特别是数据量达到PB级甚至更大的时候，即使有多台机器一起访问数据，也是很困难的。在这种情况下怎么办呢？只能放弃使用全部数据这种想法，而通过部分数据得到一个还算满意的结果，这个结果不一定是精确的，可能是不怎么精确的而基本满意，这就涉及一个“时间亚线性算法”的概念，即算法的时间复杂度低于数据量，算法运行过程中需要读取的数据量小于全部数据。

2．数据难以放入内存计算

第二个问题是数据量非常大，可能无法放进内存。一个策略是把数据放到磁盘上，基于磁盘上的数据来设计算法，这就是所谓的外存算法。学过数据结构与算法的学生对于外存算法可能不陌生，一些数据结构课程里讲过的外存排序，就是比较典型的外存算法，在数据库实现课程中讲过的一趟选择算法、两趟连接算法、嵌套循环连接算法也属于外存算法。这些外存算法的特点是以磁盘块为处理单位，其衡量标准不再是简单的CPU时间，而是磁盘的I/O。另外一个处理方法是不对全部的数据进行计算，而只向内存里放入小部分数据，仅使用内存中的小部分数据，就可以得到一个有质量保证的结果，这样的算法通常叫作“空间亚线性算法”，就是说执行这一类算法所需要的空间是小于数据本身的，即“空间亚线性”。

3．单个计算机难以保存全部数据，计算需要整体数据

在一些情况下，单个计算机难以保存或者在时间约束内处理全部数据，而计算需要整体数据，在这种情况下一个办法就是采取并行处理技术，即使用多台计算机协同工作。并行处理对应的算法是并行算法，大数据处理中常见的MapReduce就是一种大数据的编程模型，Hadoop是基于MapReduce编程模型的计算平台。

4．计算机计算能力不足或知识不足

还有一种情况是计算机的计算能力不足或者说计算所需要的知识不足。例如，判断一幅图片里是不是包含猫或者狗。这时候计算机并不知道什么是猫什么是狗，如果仅仅利用计算机而没有人的知识参与计算的话，这个问题会变得非常困难，可能要从大量的标注图像里进行学习。但如果可以让人来参与，这个问题就变得简单了。更难一点的问题，比如说两个相机哪个更好，这是一个比较主观的问题，计算机是无法判断的，怎么办呢？可以让人来参与，因此，有一类算法叫作“众包算法”，相当于把计算机难以计算但人计算相对容易的任务交给人来做，有的时候，众包算法的成本更低，算得更快。

上述是大数据算法的一些难点，针对这些难点，有一系列算法提出，包括时间亚线性算法、空间亚线性算法、外存算法、并行算法、众包算法，这些就是本书的主要内容。

1.2.5 大数据算法的应用

大数据算法在大数据的应用中将扮演什么样的角色呢？我们通过下面一些例子来看看大数据算法的应用。

1．预测中的大数据算法

如何利用大数据进行预测？一种可能的方法是从多个数据源（比如社交网络、互联网等）提取和预测主题相关的数据，然后根据预测主题建立统计模型，通过训练集学习得到模型中的参数，最后基于模型和参数进行预测。其中每一个步骤都涉及大数据算法问题。在数据获取阶段，因为从社交网络或者互联网上获取的数据量很大，所以从非结构化数据（如文本）提取出关键词或者结构化数据（例如元组、键值对）需要适用于大数据的信息提取算法；在特征选择过程中，发现预测结果和哪些因素相关需要关联规则挖掘或者主成分分析算法；在参数学习阶段，需要机器学习算法，如梯度下降等，尽管传统的机器学习有相应的算法，但是这些算法复杂度通常较高，不适合处理大数据，因此需要面向大数据的新的机器学习算法来完成任务。

2．推荐中的大数据算法

当前推荐已经成为一个热门的研究分支，有大量的推荐算法提出。由于当前商品信息和用户信息数据量都很大，例如淘宝，用户和商品的数量都达到了GB级以上，基于这样大规模的数据进行推荐需要能够处理大数据的推荐算法。例如为了减少处理数据量的SVD分解，基于以前有哪些用户购买这个商品和这些用户购买哪些商品的信息构成一个矩阵，这个矩阵规模非常大，以至于在进行推荐时无法使用，因而就需要SVD分解技术对这个矩阵分解，从而将矩阵变小。而基于这样大规模的稀疏矩阵上的推荐也需要相应的大规模矩阵操作算法。

3．商业情报分析中的大数据算法

商业情报分析首先要从互联网或者企业自身的数据仓库（例如沃尔玛PB级的数据仓库）上发现与需要分析的内容密切相关的内容，继而根据这些内容分析出有价值的商业情报，这一系列操作如果利用计算机自动完成，需要算法来解决。其中涉及的问题包括文本挖掘、机器学习，涉及的大数据算法包括分类算法、聚类分析、实体识别、时间序列分析、回归分析等，这些问题在统计学和计算机科学方面都有相关的方法提出，然而面向大数据，这些方法的性能和可扩展性难以满足要求，需要设计面向大数据的分析算法。

4．科学研究中的大数据算法

科学研究中涉及大量的统计计算，如利用回复分析发现统计量之间的相关性，利用序列分析发现演化规律。例如，美国能源部支持的项目中专门有一部分给大数据算法，在其公布的指南里包含相应的研究题目，包括如何从庞大的科学数据集合中提取有用的信息，如何发现相关数据间的关系（即相关规则发现），还包括大数据上的机器学习、数据流上的实时分析，以及数据缩减、高可控的拓展性的统计分析，这些都在科学研究中扮演重要的角色。

1.3 大数据算法设计与分析

本节对大数据算法设计与分析进行概述，蜻蜓点水地罗列一些技术，具体的技术将在后面的章节详细讲授。

1.3.1 大数据算法设计技术

1．精确算法设计方法

精确算法设计技术就是传统算法设计与分析课里讲授的算法，例如贪心法、分治法、动态规划、搜索、剪枝。这些算法设计方法也是大数据算法设计中所必需的，在本书中会经常用到这些技术。

2．并行算法

并行算法是一类很重要的大数据算法设计技术。在很多人的理解中，大数据算法就等同于并行算法，但是大数据算法不完全是并行算法。

3．近似算法

近似算法的意思是说，虽然给定计算时间，给定计算资源，对于很大的数据量无法算出精确解，但是可以退而求其次，算不那么精确的解，而且这个解的不精确程度在可以忍受的范围内。这样的设计算法有一套专门的设计技术，就是所谓的近似算法。

4．随机化算法

一种很重要的技术是随机化算法设计技术。在某些情况下，可以通过增加随机化来提高算法的效率和精度。最典型的一个技术就是抽样。虽然无法处理整个数据集合，但是可以从这个集合中抽取一小部分来处理，通过这个抽样我们就能以小见大，这一部分抽样就能够体现整个大数据集合的特征。

5．在线算法/数据流算法

所谓的在线算法或者数据流算法，指的是数据源源不断地到来，根据到来的数据返回相应的部分结果。这类算法的设计思想可以应用于两种情况：一是当数据量非常大仅能扫描一次时，可以把数据看成数据流，把扫描看成数据到来，扫描一次结束；二是数据更新非常快，不能把数据全部存下来再算结果，这时候数据也可以看成一个数据流。

6．外存算法

也有人称外存算法为I/O有效算法或者I/O高效算法。这类算法不再简单地以CPU时间作为算法时间复杂度的衡量标准，而是以I/O次数作为算法时间复杂度的判断标准，在设计算法的时候，也不是简单地以CPU时间为优化目标，而是以I/O次数尽可能少为优化目标。

7．面向新型体系结构的算法

还有一种大数据处理算法是面向特定体系结构设计的，这里的特定体系结构包括多级cache，也包括GPU和FPGA。由于这些新体系结构的特征不同，所需要的算法设计技术也不同。

8．现代优化算法

现代优化方法，包括遗传算法、模拟退火、蚁群算法、禁忌搜索等。它们在传统算法设计中的智能优化方面扮演了很重要的角色，在大数据处理算法里也有用武之地，考虑到大数据中数据量大、变化快的特点，在使用这些技术设计大数据算法时需要注意算法的可扩展性。

1.3.2 大数据算法分析技术

和传统算法分析相比，大数据算法分析尤其重要。因为在大数据上进行实验所需要的成本相对“小数据”大得多，因而完成算法计算所需的资源（时间和空间）或者某种性质（如精度）难以通过实验来得到，而必须通过理论分析来求得。当设计完一个大数据算法后，可以通过算法分析来求得所需资源（例如时间、空间或磁盘I/O）或某种性质（例如算法得到的解和精确解比例）与输入规模之间的关系，这样就可以基于算法在小规模数据上的实验结果来推演出算法在大规模数据上需要的计算资源或者某种性质所能够达到的程度，从而判定算法是否可行。对于大数据算法，主要分析如下因素：

1．时间和空间复杂度

和传统算法分析类似，大数据算法同样需要进行时间和空间复杂度分析。

2．I/O复杂度

有些情况下，大数据无法完全放入内存，必须设计外存算法，这时候需要分析磁盘I/O复杂度，即在算法运行过程中读写磁盘次数。

3．结果质量

由于大数据上的一些计算问题有时在给定的资源约束内无法精确完成，需要退而求其次，设计近似算法，在这种情况下需要分析计算结果的质量和近似比，即最优解和近似解之间的比例；对于在线算法，有时候需要分析竞争比（competitive ratio），即根据当前数据得到解的代价和知道所有数据的情况下得到解的代价相差多少。在后面章节中我们将会看到，在很多情况下，结果质量的分析往往要比结果效率的分析更复杂。

4．通信复杂度

当设计并行算法的时候，涉及多台机器，这些机器之间需要通信，这时需要知道算法运行过程中所需通信量的大小，也就是通信复杂度。

从上述介绍可以看出，大数据算法分析的内容比传统算法要丰富，也涉及更多的算法分析技术。

1.4 本书的内容

基于大数据的定义、大数据算法的定义以及大数据算法的特点，本书按照如下方式组织：

第一部分是亚线性算法，包括时间亚线性算法（第2章）和空间亚线性算法（第3章），其中包括如何利用近似算法和随机化算法设计思想来设计和分析亚线性算法。

第二部分是外存算法，将讨论如何面向外存来设计I/O有效的算法，包括外存算法概述（第4章）、外存查找结构（第5章）和外存图数据算法（第6章）。

第三部分是并行算法，由于并行算法的内容非常广泛，本书仅介绍数据密集型并行算法，包括MapReduce算法概述（第7章）、MapReduce算法例析（第8章）和超越MapReduce的并行大数据处理（第9章）。

最后，第10章介绍众包算法，讨论如何利用众包解决问题，使用众包时有哪些算法设计问题。

由于本书篇幅有限，覆盖的内容偏广，每一部分算法的例子有限，如果读者想进一步了解更多的例子，请阅读相应的文献。

习题

1.1 谈谈对“大数据”这个词的理解，以及对业界竞争关系的分析和未来发展方向的判断。

1.2 请举出需要亚线性算法的实例，并说明何种问题需要何种资源的亚线性。

1.3 请针对你所了解的推荐系统，讨论推荐系统中需要哪些大数据算法。

1.4 请说出你所接触过的最大数据量，以及在这种大数据量的数据上进行了何种计算，运用了何种大数据算法。