A framework for estimating stream expression cardinalities

Show simple item record

dc.contributor.author Dasgupta, Anirban
dc.contributor.author Langy, Kevin
dc.contributor.author Rhodesz, Lee
dc.contributor.author Thalerx, Justin
dc.date.accessioned 2016-02-12T11:22:30Z
dc.date.available 2016-02-12T11:22:30Z
dc.date.issued 2015-10
dc.identifier.citation Dasgupta, Anirban; Langy, Kevin; Rhodesz, Lee and Thalerx, Justin, “A framework for estimating stream expression cardinalities”, arXiv, Cornell University Library, DOI: arXiv:1510.01455, Oct. 2015. en_US
dc.identifier.other http://arxiv.org/abs/1510.01455
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/2087
dc.description.abstract Given [Math Processing Error] distributed data streams [Math Processing Error], we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over [Math Processing Error]. We identify a broad class of algorithms for solving this problem, and show that the estimators output by any algorithm in this class are perfectly unbiased and satisfy strong variance bounds. Our analysis unifies and generalizes a variety of earlier results in the literature. To demonstrate its generality, we describe several novel sampling algorithms in our class, and show that they achieve a novel tradeoff between accuracy, space usage, update speed, and applicability. en_US
dc.description.statementofresponsibility by Anirban Dasgupta et.al
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.subject Data Structures en_US
dc.subject Algorithms (cs.DS) en_US
dc.title A framework for estimating stream expression cardinalities en_US
dc.type Preprint en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account