Paper Info
Title
Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms
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.
Year
DOI
Venue
2022
10.1587/transfun.2021EAI0003
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
DocType
Volume
sublinear computation paradigm, big data, sublinear-time algorithms, constant-time algorithms, tester, progressive algorithms
Journal
E105A
Issue
ISSN
Citations 
3
0916-8508
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Kyohei Chiba100.34
Hiro Ito229039.95