Space-Efficient Estimation of Statistics Over Sub-Sampled Streams

dc.contributor.author McGregor, Andrew
dc.contributor.author Pavan, A.
dc.contributor.author Tirthapura, Srikanta
dc.contributor.department Electrical and Computer Engineering
dc.date 2018-02-19T07:26:42.000
dc.date.accessioned 2020-06-30T02:02:19Z
dc.date.available 2020-06-30T02:02:19Z
dc.date.copyright Thu Jan 01 00:00:00 UTC 2015
dc.date.issued 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 https://doi.org/X<a href="http://dx.doi.org/10.1007" 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/lib.dr.iastate.edu/ece_pubs/147/
dc.identifier.articleid 1152
dc.identifier.contextkey 11358157
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_pubs/147
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/20969
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/ece_pubs/147/2016_Tirthapura_SpaceEfficient.pdf|||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
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
2016_Tirthapura_SpaceEfficient.pdf
Size:
194.8 KB
Format:
Adobe Portable Document Format
Description:
Collections