2014/12/04 by Zengfeng Huang, Huang, Zengfeng, Wai Ming Tai +3
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1412.1763
arxiv created 2014/12/04 · arxiv updated 2014/12/05
The traditional requirement for a randomized streaming algorithm is just \em one-shot, i.e., algorithm should be correct (within the stated \eps-error bound) at the end of the stream. In this paper, we study the \em 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 Fp problem for any 1 < p ≤ 2, we actually only need O(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 loglog 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 Ω(log2 m) lower bound in the turnstile model, showing that the standard approach by using the union bound is essentially optimal.