Naoki Katoh - Sublinear Computation Paradigm: Algorithmic Revolution in the Big Data Era

Open Access This book is licensed under the terms of the Creative Commons Attribution 4.0 International License ( http://creativecommons.org/licenses/by/4.0/ ), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this book are included in the book's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the book's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd.

The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore

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 -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.

We deeply appreciate the members of this project and everyone else who was involved. This project was conducted as a subproject of the research project Advanced Core Technologies for Big Data Integration, which was supervised by Prof. Masaru Kitsuregawa. We would like to express our gratitude to him and everyone involved in that project. We also thank the editorial office of Springer for the opportunity to publish this book.