2026-07-23T06:23:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14181 2024-03-06T10:53:41Z ddc:004 open_access

Separations for Estimating Large Frequency Moments on Data Streams Woodruff, David P. Zhou, Samson streaming algorithms frequency moments random order lower bounds We study the classical problem of moment estimation of an underlying vector whose n coordinates are implicitly defined through a series of updates in a data stream. We show that if the updates to the vector arrive in the random-order insertion-only model, then there exist space efficient algorithms with improved dependencies on the approximation parameter ε. In particular, for any real p > 2, we first obtain an algorithm for F_p moment estimation using 𝒪̃(1/(ε^{4/p})⋅ n^{1-2/p}) bits of memory. Our techniques also give algorithms for F_p moment estimation with p > 2 on arbitrary order insertion-only and turnstile streams, using 𝒪̃(1/(ε^{4/p})⋅ n^{1-2/p}) bits of space and two passes, which is the first optimal multi-pass F_p estimation algorithm up to log n factors. Finally, we give an improved lower bound of Ω(1/(ε²)⋅ n^{1-2/p}) for one-pass insertion-only streams. Our results separate the complexity of this problem both between random and non-random orders, as well as one-pass and multi-pass streams. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David P. Woodruff and Samson Zhou 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.112 urn:nbn:de:0030-drops-141810 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.112 eng https://creativecommons.org/licenses/by/4.0/legalcode