Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms

Kyohei CHIBA
Hiro ITO

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E105-A    No.3    pp.131-141
Publication Date: 2022/03/01
Publicized: 2021/10/08
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2021EAI0003
Type of Manuscript: INVITED PAPER
Category: Algorithms and Data Structures
sublinear computation paradigm,  big data,  sublinear-time algorithms,  constant-time algorithms,  tester,  progressive algorithms,  

Full Text: FreePDF

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.