Sublinear Computation Paradigm: Algorithmic Revolution in the Big Data Era

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.

Naoki Katoh is a professor in Graduate School of Information Science at University of Hyogo, Japan, and the research director of the research project "Foundation of Innovative Algorithms for Big Data" funded by JST CREST. He had been a professor of Department of Architecture and Architectural Engineering at Kyoto University from 1997 to 2015.

Yuya Higashikawa is an associate professor in Graduate School of Information Science at University of Hyogo. He had been an assistant professor in Faculty of Science and Engineering at Chuo University from 2015 to 2018, and also a JSPS Research Fellowship for Young Scientists (PD) at Kyoto University from 2014 to 2015. He received the B. Eng, M. Eng. and Dr. Eng. degrees from Kyoto University in 2008, 2010 and 2014, respectively. His interest is on design and analysis of algorithms, combinatorial optimization, discrete mathematics, computational geometry, and operations research. He is a member of IPSJ and OR Soc. Japan.

Hiro Ito received B.E., M.E., and Ph.D. degrees from the Department of Applied Mathematics and Physics, the Faculty of Engineering, Kyoto University in 1985, 1987, and 1995, respectively. In 1987-1996, 1996-2001, and 2001-2012, he was a member of NTT Laboratories, Toyohashi University of Technology, and Kyoto University, respectively. Since 2012, he has been a full professor in the School of Informatics and Engineering at The University of Electro-Communications (UEC). He has been engaged in research on discrete algorithms mainly on graphs and networks, discrete mathematics, recreational mathematics, and algorithms for big data.

Atsuki Nagao received B.Eng., M.Info., and Ph.D degrees in Informatics in 2010, 2012, and 2015, respectively. He was an assistant professor in Faculty of Science and Technology Seikei University in 2017, and he is now an assistant professor in Faculty of Core Research Natural Science Division Ochanomizu University. He has majored in computational complexity, log-spaced algorithms and combinatorial games and puzzles.

Tetsuo Shibuya is a professor at Human Genome Center, the Institute of Medical Science, The University of Tokyo. He had been a researcher at IBM Tokyo Research Laboratory from 1997 to 2004. He had been a senior assistant professor and an associate professor at Human Genome Center, the Institute of Medical Science, the University of Tokyo from 2004 to 2009 and 2009 to 2020 respectively. He won Funai Sciences Award and Microsoft Research Japan New Faculty Award in 2011, and won Science and Technology Award from MEXT, Japan in 2021. His research interest is on bioinformatics algorithms.

Adnan Sljoka received Ph.D. in Applied Mathematics at York University in 2012. He is a leader in mathematical rigidity theory and its applications in structural and computational biology, focusing on the development of experimentally parameterized, low-computational complexity methods and algorithms for characterizing the function and dynamics of proteins. He was an Assistant Professor at Kwansei Gakuin University from 2016 to 2019 and is a visiting Professor at the University of Toronto. Currently, he is a Research Scientist at RIKEN. He is a member of Protein Society and Biophysical Society.

Kazuyuki Tanaka was born in Sendai, in 1961, and attended Tohoku University, receiving B.E. and Ph.D. degrees in Electrical Engineering from Tohoku University in 1984 and 1989, respectively. In 1989, he joined as research associate at Faculty of Engineering in Tohoku University. In 1995, he joined as associate professor in Muroran Institute of Technology, and he is now a full professor of the Graduate School of Information Sciences, Tohoku University. His interests are in probabilistic information processing and statistical machine learning as well as statistical-mechanical informatics. He is a member of Physical Society of Japan.

Yushi Uno is a professor at Graduate School of Engineering of Osaka Prefecture University, Japan. He received Ph.D. degree from Kyoto University in 1995. His research interests include algorithmic graph theory, combinatorial optimization, discrete mathematics, design and analysis of algorithms, network analysis, and so on.