An improved interactive streaming algorithm for the distinct elements problem

The exact computation of the number of distinct elements (frequency moment F0) 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 F0, F1, F2 can be approximated by efficient streaming algorithms [1], it is easy to see that exact computation of F0, F2 requires space Ω(m). In previous work, Cormode et al. [11] 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(log2m) in the case of F0) can quickly make such protocols impractical. Cormode et al. also gave a protocol with logm + 1 rounds for the exact com-putation of F0 where the space complexity is O logm log n + log2m but the total communication O ( n logm (log n + logm)). They managed to give logm round protocols with polylog(m,n) complexity for many other interesting problems in-cluding F2, Inner product, and Range-sum, but computing F0 exactly with poly-logarithmic space and communication and O(logm) rounds remained open. In this work, we give a streaming interactive protocol with logm rounds for exact computation of F0 using O (logm ( log n + logm log logm)) bits of space and the communication is O logm log n + log3m(log logm)2. The update time of the verifier per symbol received is O(log2m)