An improved interactive streaming algorithm for the distinct elements problem

DOI10.1007/978-3-662-43948-7_76MaRDI QIDQ5167803zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hartmut Klauck, Ved Prakash

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.6800

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Abstract: 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 $Omega(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 $left(O(lo{g}^{2}m);extinthecaseof;F_{0}ight)$ can quickly make such protocols impractical. Cormode et al. also gave a protocol with $logm+1$ rounds for the exact computation of $F_0$ where the space complexity is $Oleft(logmlogn+lo{g}^{2}might)$ but the total communication $Oleft(sqrtnlogmleft(logn+logmight)ight)$. They managed to give $logm$ round protocols with $operatornamepolylog(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(logm)$ rounds remained open. In this work, we give a streaming interactive protocol with $logm$ rounds for exact computation of $F_0$ using $Oleft(logmleft(,logn+logmloglogm,ight)ight)$ bits of space and the communication is $Oleft(logmleft(,logn+lo{g}^{3}m(loglogm{)}^2,ight)ight)$. The update time of the verifier per symbol received is $O(lo{g}^{2}m)$.

Recommendations

• Range‐Efficient Counting of Distinct Elements in a Massive Data Stream
• scientific article; zbMATH DE number 2019620
• Tight bounds for distributed functional monitoring

Cited in

(8)

• The landscape of communication complexity classes
• Arthur-Merlin streaming complexity
• Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Streaming Algorithms for Independent Sets
• Arthur-Merlin streaming complexity
• Beating CountSketch for heavy hitters in insertion streams
• New lower bounds in Merlin-Arthur communication and graph streaming verification

This page was built for publication: An improved interactive streaming algorithm for the distinct elements problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167803)