Space-efficient estimation of statistics over sub-sampled streams

DOI10.1007/s00453-015-9974-0zbMath1351.62026OpenAlexW1982051356WikidataQ60148561 ScholiaQ60148561MaRDI QIDQ262266

F. Blanchet-Sadri, M. Dambrine

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1152&context=ece_pubs

zbMATH Keywords

data streamsfrequency momentssub-sampling

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05)

Related Items (4)

Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Indexing for summary queries ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Space-efficient estimation of statistics over sub-sampled streams

Cites Work

• Unnamed Item
• Unnamed Item
• Space-efficient estimation of statistics over sub-sampled streams
• Processing top-\(k\) queries from samples
• Weighted random sampling with a reservoir
• Finding repeated elements
• The space complexity of approximating the frequency moments
• Finding frequent items in data streams
• Algorithms and estimators for summarization of unaggregated data streams
• The DLT priority sampling is essentially optimal
• Optimal Random Sampling from Distributed Streams Revisited
• Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums
• Priority sampling for estimation of arbitrary subset sums
• Sampling lower bounds via information theory
• Optimal approximations of the frequency moments of data streams
• Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
• Random sampling with a reservoir
• An improved data stream summary: the count-min sketch and its applications
• Continuous sampling from distributed streams

This page was built for publication: Space-efficient estimation of statistics over sub-sampled streams