
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Sublinear Computation Paradigm: ConstantTime Algorithms and Sublinear Progressive Algorithms
Kyohei CHIBA Hiro ITO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E105A
No.3
pp.131141 Publication Date: 2022/03/01 Publicized: 2021/10/08 Online ISSN: 17451337
DOI: 10.1587/transfun.2021EAI0003 Type of Manuscript: INVITED PAPER Category: Algorithms and Data Structures Keyword: sublinear computation paradigm, big data, sublineartime algorithms, constanttime algorithms, tester, progressive algorithms,
Full Text: FreePDF
Summary:
The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomialtime algorithms are practical; however, when we handle big data, even a lineartime algorithm may be too slow. Thus, sublinear and constanttime 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 constanttime 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 sublineartime, 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 constanttime algorithm and an exact algorithm (an exponentialtime one is allowed) without losing any computation time in the bigO sense.


