An Improved Interactive Streaming Algorithm for the Distinct Elements Problem

摘要

The exact computation of the number of distinct elements (frequency moment F_0) is a fundamental problem in the study of data streaming algorithms. We denote the length of the stream by n where each symbol is drawn from a universe of size m. While it is well known that the moments F_0,F_1, F_2 can be approximated by efficient streaming algorithms, it is easy to see that exact computation of F_0, F_2 requires space Ω(m). In previous work, Cormode et al. therefore considered a model where the data stream is also processed by a powerful helper, who provides an interactive proof of the result. They gave such protocols with a polylogarithmic number of rounds of communication between helper and verifier for all functions in NC. This number of rounds (O(log~2 m) in the case of F_0) can quickly make such protocols impractical. Cormode et al. also gave a protocol with log m+1 rounds for the exact computation of F_0 where the space complexity is O (log m log n + log~2 m) but the total communication 0 (n~(1/2) log m (log n + log m)). They managed to give log m round protocols with polylog (m, n) complexity for many other interesting problems including F_2, Inner product and Range-sum, but computing F_0 exactly with polylogarithmic space and communication and O(log m) rounds remained open. In this work, we give a streaming interactive protocol with log m rounds for exact computation of Fo using O (log m (log n + log m log log m)) bits of space and the communication is O (log m (log n + log~3 m(log log m)~2)). The update time of the verifier per symbol received is O(log~2 m).