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

Kyohei CHIBA; Hiro ITO

doi:10.1587/transfun.2021EAI0003

IEICE TRANSACTIONS on Fundamentals

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

Kyohei CHIBA, Hiro ITO

Full Text Views

37

Cite this

Free PDF (3.9MB)

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.

Publication: IEICE TRANSACTIONS on Fundamentals 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

Authors

Kyohei CHIBA
The University of Electro-Communications
Hiro ITO
The University of Electro-Communications

Keyword

sublinear computation paradigm, big data, sublinear-time algorithms, constant-time algorithms, tester, progressive algorithms

Cite this

Copy

Kyohei CHIBA, Hiro ITO, "Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms" in IEICE TRANSACTIONS on Fundamentals, vol. E105-A, no. 3, pp. 131-141, March 2022, doi: 10.1587/transfun.2021EAI0003.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021EAI0003/_p

Copy

@ARTICLE{e105-a_3_131,
author={Kyohei CHIBA, Hiro ITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms},
year={2022},
volume={E105-A},
number={3},
pages={131-141},
abstract={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.},
keywords={},
doi={10.1587/transfun.2021EAI0003},
ISSN={1745-1337},
month={March},}

Copy

TY - JOUR
TI - Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 131
EP - 141
AU - Kyohei CHIBA
AU - Hiro ITO
PY - 2022
DO - 10.1587/transfun.2021EAI0003
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2022
AB - 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.
ER -

IEICE TRANSACTIONS on Fundamentals