Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms
Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms
复制标题
DOI：
10.1587/transfun.2021eai0003
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kyohei Chiba;Hiro Ito
中科院分区：
文献类型：
--
作者：
Kyohei Chiba;Hiro Ito
摘要21世纪大数据带来的挑战是复杂的：在之前的常识下，我们认为多项式时间算法是实用的；然而，当我们处理大数据时，即使是线性时间算法也可能太慢。因此，需要次线性和常量时间算法。这一学术研究项目名为“大数据创新算法的基础”，于2014年启动，将于2021年9月fiNish，旨在开发各种技术和框架来设计大数据算法。在这个项目中，我们介绍了一种“次线性计算范式”。为此，我们首先对这一领域研究最多的常量时间算法进行了综述，然后介绍了我们在次线性递进算法方面的最新结果。fi-Time算法是该领域研究最多的算法之一。一种次线性渐进算法fiRST在固定时间内输出一个临时近似解，然后在次线性时间内逐步提出较好的解，finallyfiNDS精确解。我们提出了次线性递进算法理论(简称SPA理论)，它使得对于任何性质，只要它有一个恒定时间算法和一个精确算法(允许指数时间算法)，就可以得到一个次线性递进算法，而不会损失大O意义下的任何计算时间。
SUMMARY The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical; however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear-and constant-time algorithms are required. The academic research project, “Foundations of Innovative Algorithms for Big Data,” which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a “Sublinear Computation Paradigm.” Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present Sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.