Sampling from Dense Streams without Penalty

DOI10.1007/978-3-319-08783-2_2MaRDI QIDQ2920441zbMATH OpenOpenAlexFDO

Authors Vladimir Braverman, Gregory Vorsanger

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-08783-2_2

zbMATH Keywords

frequency momentsheavy hitterssamplingstreaming algorithms

Mathematics Subject Classification ID

Statistical sampling theory and related topics (62D99) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Recommendations

• Optimal Random Sampling from Distributed Streams Revisited
• Efficient sampling of non-strict turnstile data streams
• Efficient sampling of non-strict turnstile data streams
• Efficient stream sampling for variance-optimal estimation of subset sums
• \textsf{LotterySampling}: a randomized algorithm for the heavy hitters and top-\(k\) problems in data streams
• Perfect \(L_p\) sampling in a data stream
• Stream sampling for variance-optimal estimation of subset sums
• Optimal approximations of the frequency moments of data streams
• Sampling in dynamic data streams and applications
• SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS

Cited in

(8)

• Efficient sampling of non-strict turnstile data streams
• Space-efficient estimation of statistics over sub-sampled streams
• Efficient sampling of non-strict turnstile data streams
• Consistent subset sampling
• Stochastic streams: sample complexity vs. space complexity
• Stream sampling framework and application for frequency cap statistics
• 1-pass relative-error L_p-sampling with applications
• Perfect \(L_p\) sampling in a data stream

This page was built for publication: Sampling from Dense Streams without Penalty

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