Space-Efficient Estimation of Statistics Over Sub-Sampled Streams McGregor, Andrew Pavan, A. Tirthapura, Srikanta
dc.contributor.department Electrical and Computer Engineering 2018-02-19T07:26:42.000 2020-06-30T02:02:19Z 2020-06-30T02:02:19Z Thu Jan 01 00:00:00 UTC 2015 2016-02-01
dc.description.abstract <p>In many stream monitoring situations, the data arrival rate is so high that it is not even possible to observe each element of the stream. The most common solution is to subsample the data stream and use the sample to infer properties and estimate aggregates of the original stream. However, in many cases, the estimation of aggregates on the original stream cannot be accomplished through simply estimating them on the sampled stream, followed by a normalization. We present algorithms for estimating frequency moments, support size, entropy, and heavy hitters of the original stream, through a single pass over the sampled stream.</p>
dc.description.comments <p>The final publication is available at Springer via<a href="" target="_blank">10.1007/s00453-015-9974-0</a>. McGregor, Andrew, A. Pavan, Srikanta Tirthapura, and David P. Woodruff. "Space-Efficient Estimation of Statistics Over Sub-Sampled Streams." Algorithmica 74, no. 2 (2016): 787-811. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 1152
dc.identifier.contextkey 11358157
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_pubs/147
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 20:25:02 UTC 2022
dc.source.uri 10.1007/s00453-015-9974-0
dc.subject.disciplines Electrical and Computer Engineering
dc.subject.keywords data streams
dc.subject.keywords frequency moments
dc.subject.keywords sub-sampling
dc.title Space-Efficient Estimation of Statistics Over Sub-Sampled Streams
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication b0235db2-0a72-4dd1-8d5f-08e5e2e2bf7d
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
194.8 KB
Adobe Portable Document Format