This open access 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. That project ran from October 2014
to March 2020 in Japan. 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 innovative changes in algorithm theory for
big data are being pursued. For example polynomial-time algorithms have thus far been regarded
as fast but if a quadratic-time algorithm is applied to a petabyte-scale or larger big data
set problems are encountered in terms of computational resources or running time. To deal with
this critical computational and algorithmic bottleneck linear sublinear and constant time
algorithms are required. The sublinear computation paradigm is proposed here in order to
support innovation in the big data era. A foundation of innovative algorithms has been created
by developing computational procedures data structures and modelling techniques for big data.
The project is organized into three teams that focus on sublinear algorithms sublinear data
structures and sublinear modelling. The work has provided high-level academic research results
of strong computational and algorithmic interest which are presented in this book. The book
consists of five parts: Part I which consists of a single chapter on the concept of the
sublinear computation paradigm Parts II III and IV review results on sublinear algorithms
sublinear data structures and sublinear modelling respectively Part V presents application
results. The information presented here will inspire the researchers who work in the field of
modern algorithms.
