Sublinear Computation Paradigm : : Algorithmic Revolution in the Big Data Era.

• Author: Katoh, Naoki.
• TeilnehmendeR: Higashikawa, Yuya.; Ito, Hiro.; Nagao, Atsuki.; Shibuya, Tetsuo.; Sljoka, Adnan.; Tanaka, Kazuyuki.; Uno, Yushi.
• Place / Publishing House: Singapore : : Springer Singapore Pte. Limited,, 2021.; Ã2022.
• Year of Publication: 2021
• Edition: 1st ed.
• Language: English
• Physical Description: 1 online resource (403 pages)

Table of Contents

Intro -- Preface -- Contents -- Part I Introduction -- 1 What Is the Sublinear Computation Paradigm? -- 1.1 We Are in the Era of Big Data -- 1.2 Theory of Computational Complexity and Polynomial-Time Algorithms -- 1.3 Polynomial-Time Algorithms and Sublinear-Time Algorithms -- 1.3.1 A Brief History of Polynomial-Time Algorithms -- 1.3.2 Emergence of Sublinear-Time Algorithms -- 1.3.3 Property Testing and Parameter Testing -- 1.4 Ways to Decrease Computational Resources -- 1.4.1 Streaming Algorithms -- 1.4.2 Compression -- 1.4.3 Succinct Data Structures -- 1.5 Need for the Sublinear Computation Paradigm -- 1.5.1 Sublinear and Polynomial Computation Are Both Important -- 1.5.2 Research Project ABD -- 1.5.3 The Organization of This Book -- References -- Part II Sublinear Algorithms -- 2 Property Testing on Graphs and Games -- 2.1 Introduction -- 2.2 Basic Terms and Definitions for Property Testing -- 2.2.1 Graphs and the Three Models for Property Testing -- 2.2.2 Properties, Distances, and Testers -- 2.3 Important Known Results in Property Testing on Graphs -- 2.3.1 Results for the Dense-Graph Model -- 2.3.2 Results for the Bounded-Degree Model -- 2.3.3 Results for the General-Graph Model -- 2.4 Characterization of Testability on Bounded-Degree Digraphs -- 2.4.1 Bounded-Degree Model of Digraphs -- 2.4.2 Monotone Properties and Hereditary Properties -- 2.4.3 Characterizations -- 2.4.4 An Idea to Extend the Characterizations Beyond Monotone and Hereditary -- 2.5 Testable EXPTIME-Complete Games -- 2.5.1 Definitions -- 2.5.2 Testers for Generalized Chess, Shogi, and Xiangqi -- 2.6 Summary -- References -- 3 Constant-Time Algorithms for Continuous Optimization Problems -- 3.1 Introduction -- 3.2 Graph Limit Theory -- 3.3 Quadratic Function Minimization -- 3.3.1 Proof of Theorem 3.1 -- 3.4 Tensor Decomposition -- 3.4.1 Preliminaries.

3.4.2 Proof of Theorem 3.2 -- 3.4.3 Proof of Lemma 3.4 -- 3.4.4 Proof of Lemma 3.5 -- References -- 4 Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs -- 4.1 Packing and Covering Semidefinite Programs -- 4.2 Applications -- 4.2.1 SDP relaxation for Robust MaxCut -- 4.2.2 Mahalanobis Distance Learning -- 4.2.3 Related Work -- 4.3 General Framework for Packing-Covering SDPs -- 4.4 Scalar Algorithms -- 4.4.1 Scalar MWU Algorithm for (Packing-I)-(Covering-I) -- 4.4.2 Scalar Logarithmic Potential Algorithm For (Packing-I)-(Covering-I) -- 4.5 Matrix Algorithms -- 4.5.1 Matrix MWU Algorithm For (Covering-II)-(Packing-II) -- 4.5.2 Matrix Logarithmic Potential Algorithm For (Packing-I)-(Covering-I) -- 4.5.3 Matrix Logarithmic Potential Algorithm For (Packing-II)-(Covering-II) -- References -- 5 Almost Linear Time Algorithms for Some Problems on Dynamic Flow Networks -- 5.1 Introduction -- 5.2 Preliminaries -- 5.3 Objective Functions -- 5.3.1 Objective Functions for the 1-Sink Problem -- 5.3.2 Objective Functions for k-Sink -- 5.4 Minmax k-Sink Problems on Paths -- 5.4.1 Feasibility Test -- 5.4.2 Solving the 1-Sink Problem -- 5.4.3 Parametric Search Method -- 5.4.4 Sorted Matrix Method -- 5.5 Minsum k-Sink Problems on Paths -- 5.5.1 Property of Aggregate Evacuation Time -- 5.5.2 Concave Monge Property -- References -- Part III Sublinear Data Structures -- 6 Information Processing on Compressed Data -- 6.1 Restructuring Compressed Data -- 6.1.1 Preliminaries -- 6.1.2 RLBWT to LZ77 -- 6.1.3 Recompression on Grammar Compression -- 6.2 Privacy-Preserving Similarity Computation -- 6.2.1 Related Work -- 6.2.2 Edit Distance with Moves -- 6.2.3 Homomorphic Encryption -- 6.2.4 L2HE-Based Algorithm for Secure EDM -- 6.2.5 Result and Open Question -- References -- 7 Compression and Pattern Matching -- 7.1 Introduction.

7.2 History of Compressed Pattern Matching Research -- 7.3 Preliminaries -- 7.3.1 Definitions of Notation and Terms -- 7.3.2 Grammar Compression -- 7.4 Framework for Compressed Pattern Matching -- 7.4.1 KMP Method -- 7.4.2 Collage System -- 7.4.3 Pattern Matching on Collage Systems -- 7.5 Repair-VF -- 7.5.1 RePair -- 7.5.2 Outline of Repair-VF -- 7.6 MR-Repair -- 7.6.1 Maximal Repeats -- 7.6.2 MR Order -- 7.6.3 Algorithm -- 7.7 Conclusion -- References -- 8 Orthogonal Range Search Data Structures -- 8.1 Introduction -- 8.1.1 Existing Work -- 8.1.2 Our Results -- 8.2 Preliminaries -- 8.2.1 Succinct Data Structures and Information-Theoretic Lower Bound -- 8.2.2 Assumptions on Point Sets -- 8.3 kd-Tree -- 8.3.1 Construction of kd-Trees -- 8.3.2 Range Search Algorithm -- 8.3.3 Complexity Analyses -- 8.4 Wavelet Tree -- 8.4.1 Construction -- 8.4.2 Range Search Algorithm -- 8.4.3 Complexity Analyses -- 8.5 Proposed Data Structure 1: Improved Query Time Complexity -- 8.5.1 Idea for Improving the Time Complexity of the kd-Tree -- 8.5.2 Index Construction -- 8.5.3 Range Search Algorithm -- 8.5.4 Complexity Analyses -- 8.6 Proposed Data Structure 2: Succinct and Practically Fast -- 8.6.1 Index Construction -- 8.6.2 Range Search Algorithm -- 8.6.3 Complexity Analyses -- 8.7 Conclusion -- References -- 9 Enhanced RAM Simulation in Succinct Space -- 9.1 Introduction -- 9.2 Oblivious RAM -- 9.2.1 Problem -- 9.2.2 Existing Results -- 9.2.3 Tree-Based Methods -- 9.2.4 Succinct Construction -- 9.2.5 Open Problem -- 9.3 Wear Leveling -- 9.3.1 Problem -- 9.3.2 Security Refresh -- 9.3.3 Construction for Small Write Limit Cases -- 9.3.4 Open Problem -- 9.4 Conclusion -- References -- Part IV Sublinear Modelling -- 10 Review of Sublinear Modeling in Probabilistic Graphical Models by Statistical Mechanical Informatics and Statistical Machine Learning Theory.

10.1 Introduction -- 10.2 Statistical Machine Learning -- 10.2.1 Bayesian Statistics and Maximization of Marginal Likelihood -- 10.2.2 Expectation-Maximization Algorithm -- 10.2.3 Expectation-Maximization Algorithm for Probabilistic Image Segmentations -- 10.3 Statistical Mechanical Informatics -- 10.3.1 Ising Model -- 10.3.2 Advanced Mean-Field Method -- 10.3.3 Free Energy Landscapes and Phase Transitions in the Thermodynamic Limit -- 10.3.4 Ising Model on a Complete Graph -- 10.3.5 Probabilistic Segmentation by Potts Prior and Loopy Belief Propagation -- 10.3.6 Real-Space Renormalization Group Method and Sublinear Modeling of Statistical Machine Learning -- 10.4 Quantum Statistical Machine Learning -- 10.4.1 Elementary Function and Differentiations of Hermitian Matrices -- 10.4.2 Minimization of Free Energy Functionals for Density Matrices -- 10.4.3 Tensor Products -- 10.4.4 Quantum Probabilistic Graphical Models and Quantum Expectation-Maximization Algorithm -- 10.4.5 Quantum Expectation-Maximization (EM) Algorithm for Probabilistic Image Segmentation -- 10.5 Quantum Statistical Mechanical Informatics -- 10.5.1 Advanced Mean-Field Methods for the Transverse Ising Model -- 10.5.2 Real-Space Renormalization Group Method for the Transverse Ising Model -- 10.5.3 Sublinear Modeling Using a Quantum Adaptive TAP Approach and Momentum Space Renormalization Group in the Transverse Ising Model -- 10.5.4 Suzuki-Trotter Decomposition in the Transverse Ising Model -- 10.6 Concluding Remarks -- References -- 11 Empirical Bayes Method for Boltzmann Machines -- 11.1 Introduction -- 11.2 Boltzmann Machine with Prior Distributions -- 11.3 Empirical Bayes Method -- 11.4 Statistical Mechanical Analysis of Empirical Bayes Likelihood -- 11.4.1 Replica Method -- 11.4.2 Plefka Expansion -- 11.4.3 Algorithm for Hyperparameter Estimation -- 11.5 Demonstration.

11.5.1 Gaussian Prior Case -- 11.5.2 Laplace Prior Case -- 11.6 Summary and Discussion -- 11.7 Appendices -- 11.7.1 Appendix 1: Gibbs Free Energy -- 11.7.2 Appendix 2: Coefficients of Plefka Expansion -- References -- 12 Dynamical Analysis of Quantum Annealing -- 12.1 Quantum Ensembles and Their Dynamics -- 12.2 Quantum Monte Carlo Dynamics -- 12.3 Dynamical Replica Analysis -- 12.4 Simple Examples -- 12.4.1 Non-interacting Quantum Spins in a Uniform x Field -- 12.4.2 Ferromagnetic z-interactions and Uniform x and z Fields -- 12.5 Link Between Statics and Dynamics -- 12.6 Evolution on Adiabatically Separated Timescales -- 12.7 Discussion -- References -- 13 Mean-Field Analysis of Sourlas Codes with Adiabatic Reverse Annealing -- 13.1 Introduction -- 13.2 Sourlas Codes Using Quantum Fluctuations -- 13.3 Replica Analysis for Adiabatic Reverse Annealing -- 13.4 Numerical Experiments -- 13.5 Summary -- References -- Part V Applications -- 14 Structural and Functional Analysis of Proteins Using Rigidity Theory -- 14.1 Introduction -- 14.2 Protein Structural Flexibility and Dynamics -- 14.2.1 Protein Flexibility and Dynamics Is Central to Protein Function -- 14.2.2 Techniques for Analysing and Predicting Protein Flexibility and Dynamics -- 14.3 Rigidity Theory -- 14.3.1 Combinatorial Rigidity Theory and the Molecular Theorem -- 14.4 Protein Flexibility, Dynamics, and Function Analysis with Rigidity Theory -- 14.4.1 FIRST and Rigid Cluster Decomposition -- 14.4.2 Large-Scale Rigidity and Flexibility Analysis -- 14.4.3 Protein Allostery Analysis with Rigidity Theory -- 14.4.4 Using Rigidity Theory to Simulate Protein Dynamics -- 14.5 Protein Structure Validation with Rigidity Theory -- 14.6 Conclusion -- References -- 15 Optimization of Evacuation and Walking-Home Routes from Osaka City After a Nankai Megathrust Earthquake Using Road Network Big Data.

15.1 Introduction.