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.