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

Original 特约稿件机器智能研究MIR 2022-12-11

收录于合集

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

全文信息

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

樊文飞教授是国际学术界公认的在"数据库理论与系统领域都做出突破性贡献的极少数学者之一”。他是英国皇家学会计算机领域唯一的华裔院士，是在英国皇家学会具有300余年历史的签名簿上用中文签名的第一人，还是数据库领域历史上仅有的两个"大满贯"学者之一，即获得国际数据库理论与系统四大顶级会议的最佳论文奖或十年最佳论文奖(SIGMOD 2017, PODS 2015 & 2010, VLDB2010, ICDE 2007)。

樊文飞

作者故事

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

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

"对此我们提出了有界计算理论(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(英国皇家学会沃尔夫森研究优秀奖)。"

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

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

参考资料：

2019中国计算机大会

英国皇家学会院士樊文飞：把大数据变小，突破企业资源限制