Sublinear Computation Paradigm: Algorithmic Revolution in the Big Data Era
暫譯: 次線性計算範式：大數據時代的演算法革命

這本開放存取的書籍概述了一個名為「次線性計算範式」的前沿工作，該範式是在大型多年度學術研究計畫「大數據創新演算法基礎」中提出的。該計畫於2014年10月至2020年3月在日本進行。為了應對研究、產業及社會其他領域中前所未有的大數據集爆炸性增長，迫切需要開發新穎的方法和途徑來進行大數據分析。為了滿足這一需求，正在追求大數據演算法理論的創新變革。例如，至今多項式時間演算法被視為「快速」，但如果將二次時間演算法應用於一個PB級或更大的大數據集，則在計算資源或運行時間方面會遇到問題。為了解決這一關鍵的計算和演算法瓶頸，需要線性、次線性和常數時間演算法。

這裡提出次線性計算範式，以支持大數據時代的創新。通過為大數據開發計算程序、數據結構和建模技術，創建了一個創新演算法的基礎。該計畫分為三個團隊，專注於次線性演算法、次線性數據結構和次線性建模。這項工作提供了強大的計算和演算法興趣的高水平學術研究成果，這些成果在本書中呈現。

本書由五個部分組成：第一部分包含一章關於次線性計算範式的概念；第二、第三和第四部分分別回顧次線性演算法、次線性數據結構和次線性建模的結果；第五部分則呈現應用結果。這裡提供的信息將激勵在現代演算法領域工作的研究人員。

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.

Naoki Katoh 是日本兵庫大學資訊科學研究所的教授，也是由 JST CREST 資助的「大數據創新演算法基礎」研究計畫的研究主任。他曾於 1997 年至 2015 年擔任京都大學建築與建築工程系的教授。

Yuya Higashikawa 是日本兵庫大學資訊科學研究所的副教授。他曾於 2015 年至 2018 年擔任中央大學科學與工程學院的助理教授，並於 2014 年至 2015 年在京都大學擔任 JSPS 年輕科學家研究獎學金 (PD)。他於 2008 年、2010 年和 2014 年分別獲得京都大學的工學士、工學碩士和工學博士學位。他的研究興趣包括演算法的設計與分析、組合優化、離散數學、計算幾何和運籌學。他是 IPSJ 和 OR Soc. Japan 的成員。

Hiro Ito 於 1985 年、1987 年和 1995 年分別在京都大學應用數學與物理系獲得工學士、工學碩士和博士學位。在 1987 年至 1996 年、1996 年至 2001 年和 2001 年至 2012 年期間，他分別在 NTT 實驗室、豐橋技術大學和京都大學工作。自 2012 年以來，他一直是電氣通信大學 (UEC) 資訊與工程學院的正教授。他的研究主要集中在圖形和網路的離散演算法、離散數學、休閒數學以及大數據的演算法。

Atsuki Nagao 於 2010 年、2012 年和 2015 年分別獲得資訊學的工學士、資訊碩士和博士學位。他曾於 2017 年擔任成蹊大學科學與技術學院的助理教授，目前是東京女子大學自然科學核心研究部的助理教授。他的專業領域包括計算複雜性、對數間隔演算法以及組合遊戲和謎題。

Tetsuo Shibuya 是東京大學醫學科學研究所的人類基因組中心的教授。他曾於 1997 年至 2004 年在 IBM 東京研究實驗室擔任研究員。自 2004 年至 2009 年，他擔任人類基因組中心的高級助理教授，並於 2009 年至 2020 年擔任副教授。他於 2011 年獲得 Funai 科學獎和微軟研究日本新教職獎，並於 2021 年獲得日本文部科學省的科學與技術獎。他的研究興趣在於生物資訊學演算法。

Adnan Sljoka 於 2012 年在約克大學獲得應用數學博士學位。他是數學剛性理論及其在結構和計算生物學中的應用的領導者，專注於開發實驗參數化、低計算複雜度的方法和演算法，以表徵蛋白質的功能和動態。他曾於 2016 年至 2019 年在關西學院大學擔任助理教授，並且是多倫多大學的訪問教授。目前，他是 RIKEN 的研究科學家。他是蛋白質學會和生物物理學會的成員。

Kazuyuki Tanaka 於 1961 年出生於仙台，並就讀於東北大學，於 1984 年和 1989 年分別獲得東北大學的電機工程工學士和博士學位。1989 年，他加入東北大學工程學院擔任研究助理。1995 年，他成為室蘭工業大學的副教授，目前是東北大學資訊科學研究所的正教授。他的研究興趣包括概率資訊處理、統計機器學習以及統計力學資訊學。他是日本物理學會的成員。

Yushi Uno 是日本大阪府立大學工程學研究所的教授。他於 1995 年獲得京都大學的博士學位。他的研究興趣包括演算法圖論、組合優化、離散數學、演算法的設計與分析、網路分析等。