2026-07-20T11:15:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9029 2024-03-06T10:43:11Z ddc:004 open_access

Revisiting Frequency Moment Estimation in Random Order Streams Braverman, Vladimir Viola, Emanuele Woodruff, David P. Yang, Lin F. Data Stream Frequency Moments Random Order Space Complexity Insertion Only Stream We revisit one of the classic problems in the data stream literature, namely, that of estimating the frequency moments F_p for 0 < p < 2 of an underlying n-dimensional vector presented as a sequence of additive updates in a stream. It is well-known that using p-stable distributions one can approximate any of these moments up to a multiplicative (1+epsilon)-factor using O(epsilon^{-2} log n) bits of space, and this space bound is optimal up to a constant factor in the turnstile streaming model. We show that surprisingly, if one instead considers the popular random-order model of insertion-only streams, in which the updates to the underlying vector arrive in a random order, then one can beat this space bound and achieve O~(epsilon^{-2} + log n) bits of space, where the O~ hides poly(log(1/epsilon) + log log n) factors. If epsilon^{-2} ~~ log n, this represents a roughly quadratic improvement in the space achievable in turnstile streams. Our algorithm is in fact deterministic, and we show our space bound is optimal up to poly(log(1/epsilon) + log log n) factors for deterministic algorithms in the random order model. We also obtain a similar improvement in space for p = 2 whenever F_2 >~ log n * F_1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Braverman and Emanuele Viola and David P. Woodruff and Lin F. Yang 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.25 urn:nbn:de:0030-drops-90294 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.25 eng https://creativecommons.org/licenses/by/3.0/legalcode