Big data: sublinear algorithms for distributed data streams / Manuel Malatyali ; [Reviewer: Prof. Dr. Friedhelm Meyer auf der Heide, University of Paderborn, Prof. Dr. Christian Scheideler, University of Paderborn]. Paderborn, 2019
Content
- A Short Introduction
- A Monitoring Problems using Filters
- Introduction to Filter-Based Algorithms for Distributed Streams
- Model Description
- Problems Description
- Description of Filter-Based Algorithms
- Competitive Algorithms
- Related Work
- Node Existence & Domain Monitoring
- Introduction & Contribution
- Existence – One-Shot Computation
- Existence Monitoring
- Domain – One-Shot Computation
- Exact & Approximate Top-k Monitoring
- Introduction & Contribution
- Preliminaries
- Top-k-Value Monitoring
- Exact Top-k-Position Monitoring
- Discussion on Approx. Top-k-Position Monitoring
- Maximum – One-Shot Computation
- Top-K – One-Shot Computation
- Exact Top-k-Position Monitoring
- Lower Bound
- Allow the Online Algorithm to Err
- Lower Bounds for the Approx. Top-k-Monitoring Problem
- Top-k-Position Monitoring against an Approximate Offline Algorithm
- Introduction & Contribution
- Lower Bound for Competitive Algorithms
- Upper Bounds for Competitive Algorithms
- Error Augmentation
- Future Research Perspectives
- B Dynamic Algorithms
- Introduction to Dynamic Algorithms
- Fully Dynamic Algorithm for the Frequency Problem
- Introduction & Results
- Frequencies – A One-Shot Computation
- Maintaining Frequencies over Multiple Time Steps
- A Communication-Efficient Data Structure for Top-k and k-Select Queries
- Introduction & Results
- Outline of the Data Structure
- Initialization of the Data Structure
- Update
- Weak Select
- Strong Approximate k-Select
- Fully Dynamic & Filter-Based Approximate Count Distinct
- Introduction & Contribution
- Count Distinct Monitoring – One Shot
- Approximate Count Distinct Monitoring
- Future Research Perspectives