对大数据的再认识（节选）（2）

对大数据的再认识（节选）（二）

（2016年5月23日）

2、计算复杂性引起的挑战

大数据计算不能像处理小样本数据集那样做全局数据的统计分析和迭代计算，在分析大数据时，需要重新审视和研究它的可计算性、计算复杂性和求解算法。大数据样本量巨大，内在关联密切而复杂，价值密度分布极不均衡，这些特征对建立大数据计算范式提出了挑战。对于PB级的数据，即使只有线性复杂性的计算也难以实现，而且，由于数据分布的稀疏性，可能做了许多无效计算。

传统的计算复杂度是指某个问题求解时需要的时间空间与问题规模的函数关系，所谓具有多项式复杂性的算法是指当问题的规模增大时，计算时间和空间的增长速度在可容忍的范围内。传统科学计算关注的重点是，针对给定规模的问题，如何“算得快”。而在大数据应用中，尤其是流式计算中，往往对数据处理和分析的时间、空间有明确限制，比如网络服务如果回应时间超过几秒甚至几毫秒，就会丢失许多用户。大数据应用本质上是在给定的时间、空间限制下，如何“算得多”。从“算得快”到“算得多”，考虑计算复杂性的思维逻辑有很大的转变。所谓“算得多”并不是计算的数据量越大越好，需要探索从足够多的数据，到刚刚好的数据，再到有价值的数据的按需约简方法。基于大数据求解困难问题的一条思路是放弃通用解，针对特殊的限制条件求具体问题的解。人类的认知问题一般都是NP难问题，但只要数据充分多，在限制条件下可以找到十分满意的解，近几年自动驾驶汽车取得重大进展就是很好的案例。为了降低计算量，需要研究基于自举和采样的局部计算和近似方法，提出不依赖于全量数据的新型算法理论，研究适应大数据的非确定性算法等理论。

3、系统复杂性引起的挑战

大数据对计算机系统的运行效率和能耗提出了苛刻要求，大数据处理系统的效能评价与优化问题具有挑战性，不但要求理清大数据的计算复杂性与系统效率、能耗间的关系，还要综合度量系统的吞吐率、并行处理能力、作业计算精度、作业单位能耗等多种效能因素。针对大数据的价值稀疏性和访问弱局部性的特点，需要研究大数据的分布式存储和处理架构。

大数据应用涉及几乎所有的领域，大数据的优势是能在长尾应用中发现稀疏而珍贵的价值，但一种优化的计算机系统结构很难适应各种不同的需求，碎片化的应用大大增加了信息系统的复杂性，像昆虫种类一样多（500多万种）的大数据和物联网应用如何形成手机一样的巨大市场，这就是所谓“昆虫纲悖论”。为了化解计算机系统的复杂性，需要研究异构计算系统和可塑计算技术。

大数据应用中，计算机系统的负载发生了本质性变化，计算机系统结构需要革命性的重构。信息系统需要从数据围着处理器转改变为处理能力围着数据转，关注的重点不是数据加工，而是数据的搬运；系统结构设计的出发点要从重视单任务的完成时间转变到提高系统吞吐率和并行处理能力，并发执行的规模要提高到10亿级以上。构建以数据为中心的计算系统的基本思路是从根本上消除不必要的数据流动，必要的数据搬运也应由“大象搬木头”转变为“蚂蚁搬大米”。