Universal streaming of subset norms

DOI10.4086/TOC.2022.V018A020MaRDI QIDQ5040832zbMATH OpenOpenAlexFDO

Authors Vladimir Braverman, Robert Krauthgamer, Lin F. Yang

Publication date 18 October 2022

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

subset normsuniversal streaming

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Theory of computing (68Qxx) Symbolic computation and algebraic computation (68W30)

Recommendations

• Universal sketches for the frequency negative moments and other decreasing streaming sums
• Continuous monitoring of _p norms in data streams
• Turnstile streaming algorithms might as well be linear sketches
• Streaming algorithms via precision sampling
• 1-pass relative-error L_p-sampling with applications

This page was built for publication: Universal streaming of subset norms

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