Sublinear Computation Paradigm Algorithmic Revolution in the Big Data Era
This open access book gives an overview of cutting-edge work on a new paradigm called the “sublinear computation paradigm,” which was proposed in the large multiyear academic research project “Foundations of Innovative Algorithms for Big Data.” That project ran from October 2014 to March 2020, in Ja...
| Autor principal: | |
|---|---|
| Otros Autores: | , , , , , , |
| Formato: | Libro electrónico |
| Idioma: | Inglés |
| Publicado: |
Singapore :
Springer Singapore Pte. Limited
2021.
|
| Materias: | |
| Ver en Biblioteca Universitat Ramon Llull: | https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009654174406719 |
Tabla de Contenidos:
- 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
