Cover Image

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

Bibliographic Details
Main Author: Katoh, Naoki.
Other Authors: Higashikawa, Yuya., Ito, Hiro., Nagao, Atsuki., Shibuya, Tetsuo., Sljoka, Adnan., Tanaka, Kazuyuki., Uno, Yushi.
Format: eBook
Language:English
Published: Singapore : Springer Singapore Pte. Limited, 2021.
Edition:1st ed.
Subjects:
Electronic books.
Online Access:Click to View
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.

Similar Items