{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:37:13Z","timestamp":1758271033852,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2008,11]]},"abstract":"<jats:p>\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            <jats:italic>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            <jats:italic>deterministic<\/jats:italic>\n            streams, where each item is deterministically one of the domain values.\n          <\/jats:p>\n          <jats:p>\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            <jats:italic>F<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            , the second frequency moment. We present the first known streaming algorithms for estimating\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>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","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Google, Inc., New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"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"},{"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_4_1"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","year":"2004","author":"Batu T.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Burdick D.","key":"e_1_2_1_6_1"},{"volume-title":"International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Burdick D.","key":"e_1_2_1_7_1"},{"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"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Dalvi N. N.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Feigenbaum J.","key":"e_1_2_1_12_1"},{"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"},{"volume-title":"ACM-SIAM Symposium on Discrete Algorithms.","author":"Jayram T. S.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2005.1523342"},{"volume-title":"Elements of Algebra and Algebraic Computing","author":"Lipson J. D.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"volume-title":"Data Streams: Algorithms and Applications","year":"2006","author":"Muthukrishnan S.","key":"e_1_2_1_23_1"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412331.1412338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"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":"https:\/\/doi.org\/10.1145\/1412331.1412338","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}