Optimal Random Sampling from Distributed Streams Revisited

DOI10.1007/978-3-642-24100-0_27zbMATH Open1350.68051arXiv1903.12065OpenAlexW135476618WikidataQ60148584 ScholiaQ60148584MaRDI QIDQ3095333FDOQ3095333

Authors: Srikanta Tirthapura, David P. Woodruff 

Publication date: 28 October 2011

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

Abstract: We give an improved algorithm for drawing a random sample from a large data stream when the input elements are distributed across multiple sites which communicate via a central coordinator. At any point in time the set of elements held by the coordinator represent a uniform random sample from the set of all the elements observed so far. When compared with prior work, our algorithms asymptotically improve the total number of messages sent in the system as well as the computation required of the coordinator. We also present a matching lower bound, showing that our protocol sends the optimal number of messages up to a constant factor with large probability. As a byproduct, we obtain an improved algorithm for finding the heavy hitters across multiple distributed sites.

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

Recommendations

• Continuous sampling from distributed streams
• Stream sampling for variance-optimal estimation of subset sums
• Efficient stream sampling for variance-optimal estimation of subset sums
• Boosting distinct random sampling for basic counting on the union of distributed streams
• Perfect \(L_p\) sampling in a data stream
• Streaming algorithms via precision sampling
• Efficient sampling of non-strict turnstile data streams
• Efficient sampling of non-strict turnstile data streams
• Sampling in dynamic data streams and applications
• SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS

zbMATH Keywords

samplingdistributed streamsreservoir sampling

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Distributed algorithms (68W15) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Title not available (Why is that?)
• Data Streams: Algorithms and Applications
• Random sampling with a reservoir
• Title not available (Why is that?)
• Continuous sampling from distributed streams
• Optimal sampling from sliding windows
• Distributed streams algorithms for sliding windows
• Title not available (Why is that?)
• Sketching asynchronous data streams over sliding windows
• Effective computations on sliding windows
• Functional Monitoring without Monotonicity

Cited In (17)

• Space-efficient estimation of statistics over sub-sampled streams
• A general result for selecting balanced unequal probability samples from a stream
• Continuous sampling from distributed streams
• On Local Distributed Sampling and Counting
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Perfect \(L_p\) sampling in a data stream
• New algorithms for distributed sliding windows
• Efficient sampling of non-strict turnstile data streams
• Model counting meets \(F_0\) estimation
• Sampling from Dense Streams without Penalty
• Distributed monitoring of election winners
• Optimal tracking of distributed heavy hitters and quantiles
• Boosting distinct random sampling for basic counting on the union of distributed streams
• Improved algorithms for distributed entropy monitoring
• Compact samples for data dissemination
• Randomized algorithms for tracking distributed count, frequencies, and ranks
• Towards Optimal Moment Estimation in Streaming and Distributed Models

This page was built for publication: Optimal Random Sampling from Distributed Streams Revisited

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