Approximating Large Frequency Moments with Pick-and-Drop Sampling

DOI10.1007/978-3-642-40328-6_4zbMath1335.68101arXiv1212.0202OpenAlexW1863710074MaRDI QIDQ2851847

Vladimir Braverman, Rafail Ostrovsky

Publication date: 4 October 2013

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

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

zbMATH Keywords

samplingdata streamsfrequency moments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ Continuous Monitoring of l_p Norms in Data Streams

This page was built for publication: Approximating Large Frequency Moments with Pick-and-Drop Sampling