Using Additional Information in Streaming Algorithms (eBook)

Raffael Buff (Autor)

eBook Download: PDF

2016 | 1. Auflage
127 Seiten
Anchor Academic Publishing (Verlag)
978-3-96067-594-5 (ISBN)

Infos

Streaming problems are algorithmic problems that are mainly characterized by their massive input streams. Because of these data streams, the algorithms for these problems are forced to be space-efficient, as the input stream length generally exceeds the available storage. The goal of this study is to analyze the impact of additional information (more specifically, a hypothesis of the solution) on the algorithmic space complexities of several streaming problems. To this end, different streaming problems are analyzed and compared. The two problems 'most frequent item' and 'number of distinct items', with many configurations of different result accuracies and probabilities, are deeply studied. Both lower and upper bounds for the space and time complexity for deterministic and probabilistic environments are analyzed with respect to possible improvements due to additional information. The general solution search problem is compared to the decision problem where a solution hypothesis has to be satisfied.

Raffael Buff, born in 1990, holds a BSc and a MSc in Computer Science from the Swiss Federal Institute of Technology/ETH Zürich. His studies focused on topics such as Machine Learning, Big Data, Approximation Algorithms, Software Engineering and Distributed Systems. While studying, the author served as a project manager at ETH juniors - a student run consulting agency at ETH Zürich - from 2010 to 2012 and was head of the department IT at ETH juniors from 2011 to 2012. He holds the certificates ITIL Foundation and HERMES Advanced. On a sidenote, he also was Swiss Champion in Online Sudoku in 2006. Currently, the author works as a Business Consultant for an ICT company in Zürich, Switzerland.

Inhalt

List of Figures 7
List of Tables 9
Introduction 11
Overview and Structure of the Thesis 13
Structure of the Thesis 14
Related Work 15
Definitions 17
Streaming Problems and Algorithms 17
Determinism and Randomization 21
Space and Time Complexity 23
Approximation Ratio and Success Probability 24
Approximation Ratio of a Streaming Counting Problem 24
Success Probability 26
Solvability 27
Basic Calculations 29
Lower Bounds on Space Complexity 33
Introduction to Communication Complexity 33
Lower Bound for General Streaming Problems 35
Lower Bound for an Exact Deterministic Streaming Problem 35
Lower Bound for an Exact Probabilistic Streaming Problem 36
Lower Bound for an Approximative Deterministic Streaming Problem 38
Lower Bound for an Approximative Probabilistic Streaming Problem 39
Lower Bounds for Hypotheses Verifications 41
Most Frequent Item Problem 45
General Streaming Problem Analysis 45
Exact Deterministic Most Frequent Item Problem 45
Exact Probabilistic Most Frequent Item Problem 55
Approximative Deterministic Most Frequent Item Problem 62
Approximative Probabilistic Most Frequent Item Problem 74
Summary of the General Most Frequent Item Problem 80
Hypothesis Verification Analysis 82
Analysis Conclusion 88
Number of Distinct Items Problem 89
General Streaming Problem Analysis 89
Exact Deterministic Number of Distinct Items Problem 89
Exact Probabilistic Number of Distinct Items Problem 93
Approximative Deterministic Number of Distinct Items Problem 95
Approximative Probabilistic Number of Distinct Items Problem 100
Summary of the General Number of Distinct Items Problem 110
Hypothesis Verification Analysis 112
Verification of All Possible Hypotheses 112
Justification of One Correct Hypothesis 116
Analysis Conclusion 117
Conclusion 119
Summary 119
Conclusion 121
Future Work 121

Produkt-Details

• Erscheint lt. Verlag: 8.12.2016
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• ISBN-10: 3-96067-594-1 / 3960675941
• ISBN-13: 978-3-96067-594-5 / 9783960675945