Using Additional Information in Streaming Algorithms
(Sprache: Englisch)
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...
Voraussichtlich lieferbar in 3 Tag(en)
versandkostenfrei
Buch (Kartoniert)
41.20 €
- Lastschrift, Kreditkarte, Paypal, Rechnung
- Kostenlose Rücksendung
Produktdetails
Produktinformationen zu „Using Additional Information in Streaming Algorithms “
Klappentext zu „Using Additional Information in Streaming Algorithms “
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.
Lese-Probe zu „Using Additional Information in Streaming Algorithms “
Text sample:Chapter 4 Lower Bounds on Space Complexity:
For every streaming problem S, we want to analyze both upper and lower bounds for the achievable space complexity. For the upper bound, one has to find a certain streaming algorithm that solves S. Such an algorithm can afterwards be analyzed with respect to its required space and time complexities. To prove a lower bound on the space complexity, the technique of communication complexity theory is used, which is described by Hromkovic [Hro97] or in the initial paper by Yao [Yao79].
4.1 Introduction to Communication Complexity:
Communication complexity is a study area that tries to identify the required communication for a distributed algorithmic problem. The most common model is the two-computer model, in which two distributed computers have to calculate a certain function value. Both computers have a part of the input value and have unbounded computation power and storage resources, but a limited communication channel to each other. The main question is: How many communication bits do the two computers have to exchange to calculate the function value for a given input value separation? With this model, it is possible to mathematically analyze lower bounds on the communication complexity.
One special type of the communication complexity is the one-way communication. In this model, we have two computers, named as the left one CL and the right one CR, both having a part of the input value. In the one-way communication model, only the left computer is allowed to communicate to the other computer. To evaluate a certain function on the distributed input value, the left computer processes its input value part and transmits some communication. The right computer uses this communication and the second input value part to compute the function.
Obviously, if the left computer transmits its whole input value part, the right computer can easily evaluate the correct output value, as it has unbounded storage and
... mehr
computation resources. For some functions, the output value can be computed with a significantly lower communication complexity. For example, if one wants to identify the highest integer of a certain set of integers as input values, that is distributed among the two computers, the left computer can just communicate its maximal integer and the right computer outputs the correct output value easily. With this approach, we have a space complexity of one integer instead of communicating the whole input value part.
For this model of one-way communication, we can define a fooling set that allows us to prove a certain communication complexity lower bound. The idea of a fooling set is to list some input value candidates, that force any algorithm to use different communications from CL to CR in order to distinguish these input value candidates. This concept of one-way communication between two computers can be transformed to a streaming problem setting where we can prove a certain space complexity lower bound. In the following, we will define two fooling set concepts and prove in the following section why these fooling sets imply a space complexity lower bound for streaming problems.
But first, we have to define the deterministic one-way communication more formally: [...].
One can define a fooling set for the one-way communication complexity as the combination of a set of representatives and a test set. The representatives are located at the left computer, the tests at the right one. Such a combination is called a fooling set if, for every two representatives, there is at least one test such that the communication from CL to CR has to be different. This is the case if the correct algorithm has to compute two different output values for these two representatives combined with the same test entry. This communication complexity concept can be used to prove space complexity lower bounds for streaming problems. Formally, a fooling set for a streaming problem is defined as follows [.
For this model of one-way communication, we can define a fooling set that allows us to prove a certain communication complexity lower bound. The idea of a fooling set is to list some input value candidates, that force any algorithm to use different communications from CL to CR in order to distinguish these input value candidates. This concept of one-way communication between two computers can be transformed to a streaming problem setting where we can prove a certain space complexity lower bound. In the following, we will define two fooling set concepts and prove in the following section why these fooling sets imply a space complexity lower bound for streaming problems.
But first, we have to define the deterministic one-way communication more formally: [...].
One can define a fooling set for the one-way communication complexity as the combination of a set of representatives and a test set. The representatives are located at the left computer, the tests at the right one. Such a combination is called a fooling set if, for every two representatives, there is at least one test such that the communication from CL to CR has to be different. This is the case if the correct algorithm has to compute two different output values for these two representatives combined with the same test entry. This communication complexity concept can be used to prove space complexity lower bounds for streaming problems. Formally, a fooling set for a streaming problem is defined as follows [.
... weniger
Autoren-Porträt von Raffael Buff
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.
Bibliographische Angaben
- Autor: Raffael Buff
- 2016, 132 Seiten, 8 Abbildungen, Maße: 15,5 x 22 cm, Kartoniert (TB), Englisch
- Verlag: Anchor Academic Publishing
- ISBN-10: 396067094X
- ISBN-13: 9783960670940
Sprache:
Englisch
Kommentar zu "Using Additional Information in Streaming Algorithms"
Schreiben Sie einen Kommentar zu "Using Additional Information in Streaming Algorithms".
Kommentar verfassen