Applying approximate counting for computing the frequency moments of long data streams

DOI10.1007/S00224-007-9048-ZMaRDI QIDQ2272207zbMATH OpenOpenAlexFDO

Authors André Gronemeier, Martin Sauerhoff

Publication date 6 August 2009

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

Full work available at URL https://doi.org/10.1007/s00224-007-9048-z

zbMATH Keywords

constant error parameters

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Optimal approximations of the frequency moments of data streams
• An improved data stream algorithm for frequency moments
• The space complexity of approximating the frequency moments
• scientific article; zbMATH DE number 1256715
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• An improved data stream algorithm for frequency moments
• An information statistics approach to data stream and communication complexity
• Approximate counting: a detailed analysis
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Counting large numbers of events in small registers
• Data streams: algorithms and applications.
• Optimal approximations of the frequency moments of data streams
• Optimal space lower bounds for all frequency moments
• Random sampling with a reservoir
• Simpler algorithm for estimating frequency moments of data streams
• The space complexity of approximating the frequency moments

Cited in

(4)

• Deterministically Estimating Data Stream Frequencies
• An improved data stream algorithm for frequency moments
• A Modular CDF Approach for the Approximation of Percentiles
• The value of multiple read/write streams for approximating frequency moments

This page was built for publication: Applying approximate counting for computing the frequency moments of long data streams

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