The traditional requirement for a randomized streaming algorithm is just one-shot, i.e., algorithm should be correct (within the stated ε-error bound) at the end of the stream. In this paper, we study the tracking problem, where the output should be correct at all times. The standard approach for solving the tracking problem is to run O(log m) independent instances of the one-shot algorithm and apply the union bound to all m time instances. In this paper, we study if this standard approach can be improved, for the classical frequency moment problem. We show that for the F_p problem for any 1 p ≤ 2, we actually only need Ο(log log m + log n) copies to achieve the tracking guarantee in the cash register model, where n is the universe size. Meanwhile, we present a lower bound of Ω...[ Read more ]

The traditional requirement for a randomized streaming algorithm is just one-shot, i.e., algorithm should be correct (within the stated ε-error bound) at the end of the stream. In this paper, we study the tracking problem, where the output should be correct at all times. The standard approach for solving the tracking problem is to run O(log m) independent instances of the one-shot algorithm and apply the union bound to all m time instances. In this paper, we study if this standard approach can be improved, for the classical frequency moment problem. We show that for the F_p problem for any 1 < p ≤ 2, we actually only need Ο(log log m + log n) copies to achieve the tracking guarantee in the cash register model, where n is the universe size. Meanwhile, we present a lower bound of Ω(log m log log m) bits for all linear sketches achieving this guarantee. This shows that our upper bound is tight when n = (log m)^O(1). We also present an Ω(log² m) lower bound in the turnstile model, showing that the standard approach by using the union bound is essentially optimal.