Streaming algorithms with one-sided estimation

DOI10.1007/978-3-642-22935-0_37MaRDI QIDQ3088116zbMATH OpenOpenAlexFDO

Authors Joshua Brody, David P. Woodruff

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_37

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Streaming Algorithms Measured in Terms of the Computed Quantity
• Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)
• Estimating the sortedness of a data stream
• A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
• Optimal space lower bounds for all frequency moments

Cites work

• 1-pass relative-error L_p-sampling with applications
• Algorithms for dynamic geometric problems over data streams
• An improved data stream summary: the count-min sketch and its applications
• Communication Complexity
• Data Streams: Algorithms and Applications
• Efficient Sketches for Earth-Mover Distance, with Applications
• Estimating the sortedness of a data stream
• Estimation of the number of vertices of different degrees in a graph
• Forbidden Intersections
• scientific article; zbMATH DE number 5764793 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• Sublinear optimization for machine learning
• The Data Stream Space Complexity of Cascaded Norms

Cited in

(2)

• Streaming Algorithms Measured in Terms of the Computed Quantity
• One-sided error communication complexity of gap Hamming distance

This page was built for publication: Streaming algorithms with one-sided estimation

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