Tight lower bound for linear sketches of moments

DOI10.1007/978-3-642-39206-1_3MaRDI QIDQ5326547zbMATH OpenOpenAlexFDO

Authors

Publication date 6 August 2013

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the $p^{mth}$ moment, for $pin(0,2]$ has been settled [KNW10], for $p>2$ the exact complexity remains open. For $p>2$ the current best algorithm uses $O(n^{1-2/p}logn)$ words of space [AKO11,BO10], whereas the lower bound is of $Omega(n^{1-2/p})$ [BJKS04]. In this paper, we show a tight lower bound of $Omega(n^{1-2/p}logn)$ words for the class of algorithms based on linear sketches, which store only a sketch $Ax$ of input vector $x$ and some (possibly randomized) matrix $A$. We note that all known algorithms for this problem are linear sketches.

Recommendations

• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• On Estimating Frequency Moments of Data Streams
• Optimal space lower bounds for all frequency moments
• High probability frequency moment sketches
• Optimal approximations of the frequency moments of data streams

Cited in

(10)

• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• scientific article; zbMATH DE number 7049740 (Why is no real title available?)
• Turnstile streaming algorithms might as well be linear sketches
• On approximating matrix norms in data streams
• Arithmetic sketching
• On randomized sketching algorithms and the Tracy-Widom law
• Taylor polynomial estimator for estimating frequency moments
• High probability frequency moment sketches
• On sketching the \(q\) to \(p\) norms
• The Simultaneous Communication of Disjointness with Applications to Data Streams

This page was built for publication: Tight lower bound for linear sketches of moments

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