Sublinear Computation Paradigm : (Record no. 308638)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 11186nam a22005293i 4500 |
| 001 - CONTROL NUMBER | |
| control field | EBC6787726 |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20240122001458.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS | |
| fixed length control field | m o d | |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr cnu|||||||| |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 231124s2021 xx o ||||0 eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9789811640957 |
| Qualifying information | (electronic bk.) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 9789811640940 |
| 035 ## - SYSTEM CONTROL NUMBER | |
| System control number | (MiAaPQ)EBC6787726 |
| 035 ## - SYSTEM CONTROL NUMBER | |
| System control number | (Au-PeEL)EBL6787726 |
| 035 ## - SYSTEM CONTROL NUMBER | |
| System control number | (OCoLC)1314627511 |
| 040 ## - CATALOGING SOURCE | |
| Original cataloging agency | MiAaPQ |
| Language of cataloging | eng |
| Description conventions | rda |
| -- | pn |
| Transcribing agency | MiAaPQ |
| Modifying agency | MiAaPQ |
| 050 #4 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | QA75.5-76.95 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Katoh, Naoki. |
| 245 10 - TITLE STATEMENT | |
| Title | Sublinear Computation Paradigm : |
| Remainder of title | Algorithmic Revolution in the Big Data Era. |
| 250 ## - EDITION STATEMENT | |
| Edition statement | 1st ed. |
| 264 #1 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE | |
| Place of production, publication, distribution, manufacture | Singapore : |
| Name of producer, publisher, distributor, manufacturer | Springer Singapore Pte. Limited, |
| Date of production, publication, distribution, manufacture, or copyright notice | 2021. |
| 264 #4 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE | |
| Date of production, publication, distribution, manufacture, or copyright notice | �2022. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 online resource (403 pages) |
| 336 ## - CONTENT TYPE | |
| Content type term | text |
| Content type code | txt |
| Source | rdacontent |
| 337 ## - MEDIA TYPE | |
| Media type term | computer |
| Media type code | c |
| Source | rdamedia |
| 338 ## - CARRIER TYPE | |
| Carrier type term | online resource |
| Carrier type code | cr |
| Source | rdacarrier |
| 505 0# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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. |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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. |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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. |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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. |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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. |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 15.1 Introduction. |
| 588 ## - SOURCE OF DESCRIPTION NOTE | |
| Source of description note | Description based on publisher supplied metadata and other sources. |
| 590 ## - LOCAL NOTE (RLIN) | |
| Local note | Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2023. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries. |
| 655 #4 - INDEX TERM--GENRE/FORM | |
| Genre/form data or focus term | Electronic books. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Higashikawa, Yuya. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Ito, Hiro. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Nagao, Atsuki. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Shibuya, Tetsuo. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Sljoka, Adnan. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Tanaka, Kazuyuki. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Uno, Yushi. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Relationship information | Print version: |
| Main entry heading | Katoh, Naoki |
| Title | Sublinear Computation Paradigm |
| Place, publisher, and date of publication | Singapore : Springer Singapore Pte. Limited,c2021 |
| International Standard Book Number | 9789811640940 |
| 797 2# - LOCAL ADDED ENTRY--CORPORATE NAME (RLIN) | |
| Corporate name or jurisdiction name as entry element | ProQuest (Firm) |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | <a href="https://ebookcentral.proquest.com/lib/bacm-ebooks/detail.action?docID=6787726">https://ebookcentral.proquest.com/lib/bacm-ebooks/detail.action?docID=6787726</a> |
| Public note | Click to View |
No items available.