Derandomization for Sliding Window Algorithms with Strict Correctness
| Autor: | Danny Hucke, Markus Lohrey, Moses Ganardi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Data stream
Correctness Sublinear function Computer science Value (computer science) Window (computing) 0102 computer and information sciences 02 engineering and technology Space (mathematics) 01 natural sciences 010201 computation theory & mathematics Sliding window protocol Theory of computation 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm |
| Zdroj: | Computer Science – Theory and Applications ISBN: 9783030199548 CSR |
| DOI: | 10.1007/978-3-030-19955-5_21 |
| Popis: | In the sliding window streaming model the goal is to compute an output value that only depends on the last n symbols from the data stream. Thereby, only space sublinear in the window size n should be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instant t, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called “strict correctness” in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|