今天听了一场报告会，是清华计算机系60周年系列讲座之一，主讲人是哈工大软院院长李建中教授，主题《计算和数据资源受限的大数据计算的复杂性理论与高效算法研究》，李老师介绍的大数据计算理论体系很完善，由于只有一个小时，很多只能稍微提及，但是还是有很多观点让我受益匪浅，分享一下。
本文预计阅读时间 5 分钟。
什么是大数据？
wiki定义：Big data is data sets that are so big and complex that traditional data-processing application software are inadequate to deal with them.
首先大数据指的是数据集，是纯粹的数据。其次，由于复杂与庞大，传统的数据处理软件无法处理。这样的数据集就可以叫大数据。
这个定义其实很模糊，什么叫传统的数据处理软件无法处理的？也没规定硬件。那超级计算机能处理的算不算？普通的CPU、内存，后面接一个存储柜装个几百 T 数据算不算大数据呢？
因此，个人感觉，应该是普通PC机的配置，256内存，12T硬盘，用传统的数据库Oracle，MySQL不好用了，感觉单机撑不下了，或者单表数据量几百万以上性能急剧下降无法满足要求了。这时候就叫传统的搞不定了，需要考虑大数据解决方案了。
大数据计算问题
输入：大数据 D，问题 P 的参数
输出：问题 P 的解 P(D)
这里重点是输入一个大数据。有一个很容易混淆的场景是拥有的数据量很大，TB、PB级，但是每次用来计算的只有几十或几百MB，这个输入就不能称为大数据，因此这种问题就不是大数据计算问题。
你面临的问题不是大数据计算问题有什么问题吗？没什么问题，如果真碰到了大数据计算问题就麻烦了。
由此也给出大数据计算的定义：
大数据计算：求解大数据计算问题的过程。
大数据计算的挑战
报告的前提是“计算和数据资源受限”，为什么这个很重要呢？因为一般情况下这是搞大数据的都会面临的实际问题，如果一个人说他的大数据场景没这种问题，很有可能他的数据不够大。下面看看受限的两个方面：
1、计算资源的强受限性
先不说简单的计算，只说遍历一遍数据。
大数据一般指 TB、PB、EB、ZB、YB 级别的数据。以机械硬盘和 SSD 的 IO 速率来考虑。1TB的数据遍历一遍（顺序读取），机械硬盘1G/s，需要17分钟，SSD算5G/s，需要3分钟。
一个的算法至少需要将所有数据遍历一遍。因此这个时间可以认为是处理大数据的少时间，那么 1PB 数据用 SSD 遍历就需要 2 天多，而且 1PB 的SSD 成本相当大，估计没有人这么搞。数据量再大还得继续乘 1024。
多项式时间不再是大数据计算问题易解性的判别标准。对于PB、EB需要至少亚多项式，对于ZB、YB至少需要polylog多项式时间才算易解。
2、数据资源弱可用性
这个特性主要说的是数据质量差。理想中数据应该是整整齐齐的，但是实际上数据很多都会有错误，大概有10%左右的错误数据。人工记录的数据就可能由于脑子进水记错了。数据错误会造成很大经济损失。
既然数据有错的，那么能不能修正呢？修复的复杂度是n^3数量级的，很难修复。因此，修复后的数据也不会正确。这个叫弱可用性数据，如何在弱可用性数据上进行计算，使结果的误差满足要求，是另一个重要的研究方向。
一些计算方法
1、小数据近似大数据
所谓大事化小，小事化了。需要发现大数据的内在规律，才能将问题简化，这个就跟具体问题十分相关了，没啥通用方法。类似把123*234*345*0化简为1*0。
2、增量计算方法
将需要计算的数据分成很多小份，一份一份算。不过这个需要计算具有可加性。比如给 1 万个数求和，先分 10 份，每份 1 千个数求和，再给 10 个和求和。
3、直接处理压缩数据
将 100T 数据压缩为1G，在1G数据上直接设计算法就会容易很多。但是如果要达到在 100T 上数据计算的效果，需要压缩方法具有映射完整性，也就是100T数据能完全对应到 1G 上，1G 数据也能完全恢复为 100T 数据。举个例子：1，1，1，1，1，压缩为5，1。
大数据系统
这部分回到我们经常听到的 Hadoop，MapReduce，Spark了。这些是大数据计算框架，但是只有这个是不够的，在面对一个问题时主要需要解决的还是算法问题。
举个例子：大数据计算框架就像包工队，他们有盖1万层高楼的能力，这是传统包工队干不了的。但没有图纸是没法盖出楼来的。而图纸就是算法。
总结
大数据是指传统方法处理不了的数据集。大数据计算问题处理的是大数据。计算受限和数据受限是大数据计算中普遍存在的客观现象。这时对于一个大数据计算问题的复杂度分析就很重要，到底能不能计算，多长时间能计算出来，算出来的结果准不准，都需要理论支持。
