Using Additional Information in Streaming Algorithmsdiplom.de, 8 déc. 2016 - 127 pages 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. |
Table des matières
1 | |
5 | |
Definitions | 7 |
Lower Bounds on Space Complexity | 23 |
Most Frequent Item Problem | 35 |
Number of Distinct Items Problem | 79 |
Conclusion | 109 |
Autres éditions - Tout afficher
Expressions et termes fréquents
allowed analysis approach approximation ratio assume basic transformation bit string cache calculate the space Chapter choose communication complexity complexity lower bound concept conclude consequence contains Corollary correct corresponding data stream decision problem decrease define definition described distinct items problem efficiently equal exactly factor fixed Fm<n fooling set formally frac frequent item problem function further given highest frequency hypothesis verification identify Illustration implies inequality input stream input values introduced known leads least length log2 min{n namely number of distinct optimal output value possible present probabilistic setting probability distribution processes produce proof prove random representatives respectively result samples Similarly simple solution solves space complexity lower spacer items storage streaming algorithm streaming counting problem streaming problem success probability technique term test entry test set Theorem 4.3 thesis upper bound valid verify