Sublinear Computation Paradigm: Algorithmic Revolution in the Big Data Era

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
	15.2 Quickest Evacuation Planning Problem
		15.2.1 Dynamic Network
		15.2.2 Time-Expanded Network
		15.2.3 Algorithm for Solving Quickest Evacuation Planning Problem
	15.3 Pedestrian Simulation Model
	15.4 Data Preparation
		15.4.1 Road Network
		15.4.2 Tsunami Evacuation Buildings
		15.4.3 Daytime Population
		15.4.4 Decisions on Number of People Struggling to Return Home and Number of Evacuees
	15.5 Simplifying and Restoring Large Road Network  for Route Optimization
		15.5.1 Simplification of Road Network
		15.5.2 Restoring Optimized Routes on Original Road Network
	15.6 Route Optimization Settings
		15.6.1 Optimization Steps
		15.6.2 Computational Conditions
	15.7 Results of Route Optimization
		15.7.1 Computational Times
		15.7.2 Reproducibility of Restored Routes
		15.7.3 Optimization Results
	15.8 Conclusion
	References
16 Stream-Based Lossless Data Compression
	16.1 Introduction to Stream-Based Data Compression
	16.2 Stream-Based Lossless Data Compression with Static Look-Up Table
		16.2.1 Design of LCA-SLT
		16.2.2 Implementation of LCA-SLT
		16.2.3 Performance Evaluations
	16.3 Stream-Based Lossless Data Compression  with Dynamic Look-Up Table
		16.3.1 Design of LCA-DLT
		16.3.2 Implementation of LCA-DLT
		16.3.3 Performance Evaluations
	16.4 Optimization Techniques for LCA-DLT
		16.4.1 Lazy Management of Look-Up Tables
		16.4.2 Time-Sharing Multithreading on Compression
	16.5 Related Works and Literatures
	References