Sublinear Computation Paradigm

Abstract

This book gives an overview of cutting-edge work on a new paradigm called the “sublinear computation paradigm,” which was proposed in the large multiyear academic research project “Foundations of Innovative Algorithms for Big Data” in Japan. In today's rapidly evolving age of big data, massive increases in big data have led to many new opportunities and uncharted areas of exploration, but have also brought new challenges. To handle the unprecedented explosion of big data sets in research, industry, and other areas of society, there is an urgent need to develop novel methods and approaches for big data analysis. To meet this need, we are pursuing innovative changes in algorithm theory for big data. For example, polynomial-time algorithms have thus far been regarded as “fast,” but if we apply an Oðn2Þ-time algorithm to a petabyte-scale or larger big data set, we will encounter problems in terms of computational resources or running time. To deal with this critical computational and algorithmic bottleneck, we require linear, sublinear, and constant-time algorithms. In this project, which ran from October 2014 to September 2021, we have proposed the sublinear computation paradigm in order to support innovation in the big data era. We have created a foundation of innovative algorithms by developing computational procedures, data structures, and modeling techniques for big data. The project is organized into three teams that focus on sublinear algorithms, sublinear data structures, and sublinear modeling. Our work has provided high-level academic research results of strong computational and algorithmic interest, which are presented in this book. This book consists of five parts: Part I, which consists of a single chapter introducing the concept of the sublinear computation paradigm; Parts II, III, and IV review results on sublinear algorithms, sublinear data structures, and sublinear modeling, respectively; and Part V presents some application results