{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T23:57:33Z","timestamp":1648771053613},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2008,11]]},"abstract":"\n The probabilistic stream model was introduced by Jayram et al. [2007]. It is a generalization of the data stream model that is suited to handling\n probabilistic<\/jats:italic>\n data, where each item of the stream represents a probability distribution over a set of possible events. Therefore, a probabilistic stream determines a distribution over a potentially exponential number of classical\n deterministic<\/jats:italic>\n streams, where each item is deterministically one of the domain values.\n <\/jats:p>\n \n We present algorithms for computing commonly used aggregates on a probabilistic stream. We present the first one pass streaming algorithms for estimating the expected mean of a probabilistic stream. Next, we consider the problem of estimating frequency moments for probabilistic data. We propose a general approach to obtain unbiased estimators working over probabilistic data by utilizing unbiased estimators designed for standard streams. Applying this approach, we extend a classical data stream algorithm to obtain a one-pass algorithm for estimating\n F<\/jats:italic>\n 2<\/jats:sub>\n , the second frequency moment. We present the first known streaming algorithms for estimating\n F<\/jats:italic>\n 0<\/jats:sub>\n , the number of distinct items on probabilistic streams. Our work also gives an efficient one-pass algorithm for estimating the median, and a two-pass algorithm for estimating the range.\n <\/jats:p>","DOI":"10.1145\/1412331.1412338","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-30","source":"Crossref","is-referenced-by-count":20,"title":["Estimating statistical aggregates on probabilistic data streams"],"prefix":"10.1145","volume":"33","author":[{"given":"T. S.","family":"Jayram","sequence":"first","affiliation":[{"name":"IBM Almaden Research, Almaden, CA"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, Amherst, MA"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Google, Inc., New York, NY"}]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007701"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science. 1--10","author":"Bar-Yossef Z."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Batu T.","year":"2004"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Burdick D."},{"key":"e_1_2_1_7_1","volume-title":"International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Burdick D."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109685"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247513"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Dalvi N. N."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Feigenbaum J."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_17_1","unstructured":"Guha S. and McGregor A. 2007. Space-efficient sampling. In AISTATS. 169--176. Guha S. and McGregor A. 2007. Space-efficient sampling. In AISTATS. 169--176."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_2_1_19_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms.","author":"Jayram T. S."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2005.1523342"},{"key":"e_1_2_1_21_1","volume-title":"Elements of Algebra and Algebraic Computing","author":"Lipson J. D."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_23_1","volume-title":"Data Streams: Algorithms and Applications","author":"Muthukrishnan S.","year":"2006"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412331.1412338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T21:31:35Z","timestamp":1613770295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1412331.1412338"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412331.1412338","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":["Information Systems"],"published":{"date-parts":[[2008,11]]}}}