爱丁堡大学樊文飞 | 有界计算理论: 在有限资源下查询大数据

论文题名：Bounded Evaluation: Querying Big Data with Bounded Resources

论文作者：Yang Cao, Wen-Fei Fan, Teng-Fei Yuan

全文链接：https://link.springer.com/article/10.1007/s11633-020-1236-1  

参考链接：https://mp.weixin.qq.com/s/5G73V4orMf1cT9mY73PClQ

大数据分析通常代价高昂，而且被认为是拥有大型集群计算机的大公司的特权。2019年CNCC大会上，英国皇家学会院士樊文飞教授做了题为"把大数据做小"的主旨报告，基于有界计算理论和一个数据驱动近似方案，他提出一种新的有限资源式查询处理范式，可为小公司提供即时查询大数据的能力。2020年8月，樊文飞教授在IJAC发表最新研究成果"有界计算理论：在有限资源下查询大数据"，将大数据的查询简化为对小数据的计算，从而使在有限资源下查询大数据成为可能，全文开放获取！

图片来自Springer

作者故事：

一次采访中，樊文飞教授表示:

"我们是否可以通过理论的突破到系统的落地，解决大多数企业因资源受限无力从事真正的大数据计算的现实问题？是否可以通过’‘把大数据变小’‘，做到企业无论大小都能享受大数据分析的利益？"

"对此我们提出了有界计算理论(bounded evaluation)及数据驱动的近似计算(data-driven approximation)理论。"

有界计算理论的基本思想是，给定一个函数F(x)，参数x代表大数据集。多数计算不需要访问全部的x、只需要取x的一小部分就能得到F(x)的精确解。有界计算理论研究的就是如何根据不同的函数F，根据语义找到所需的x的那一小部分。

"一家世界一流的公司通过测试发现，在数十亿条数据的实时查询场景下，91%的查询可以用有界计算来解决；并在70%以上的查询中，查询效率提升25倍到14万倍。剩余9%不具备有界计算条件的查询，可以通过数据驱动的近似计算理论来解决。"数据驱动的近似计算是根据用户的查询，在数据的层次表述中动态找到所需的数据，并在有限资源下计算查询的近似解。其特点是保证精确度，即对每个精确解，都找到一个对应的近似解使得二者之间的误差在一定范围内，同时每个近似解都对应一个误差范围内的精确解。国际上还没有查询系统能做到这一点。"

"比如你要在北京找一个离艺术馆比较近的、价格低于500元的旅馆，在资源有限的情况下只能查看一百条数据，那么我们就可以给你一个近似的结果，可能这个旅馆是520元，也可能是距离一个美术馆比较近的旅馆，但保证每个近似解都是相关的，而且每一个精确解都能被覆盖到。"

"上面提到的这家世界一流的公司认为，有界计算是一个具有突破性的高潜力发明，并决定每年投资上千万人民币支持开放性的基础研究。"樊文飞介绍，"此外，这项工作还在2018年拿了Royal Society Wolfson Research Merit Award(英国皇家学会沃尔夫森研究优秀奖)。"

什么是创新？创新包括探索新领域、发现新问题、找到新方法、或者借鉴其他领域的解决方法解决本领域的问题，这是创新程度的一个评判标准。

樊文飞说:"我们所谓的创新，关键不是看你发了多少论文、在哪里发表、引用率有多高。学术地位是由学术界的口碑决定的，是你能否提出基础、原创的东西，能够引领学术界，并在工业界落地。" 

来源：《International Journal of Automation and Computing》编辑部