{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:53Z","timestamp":1778807873043,"version":"3.51.4"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["414852"],"award-info":[{"award-number":["414852"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"RPC","award":["HKUST"],"award-info":[{"award-number":["HKUST"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>\n            A fundamental problem in data management is to draw and maintain a sample of a large data set, for approximate query answering, selectivity estimation, and query planning. With large, streaming data sets, this problem becomes particularly difficult when the data is shared across multiple distributed sites. The main challenge is to ensure that a sample is drawn uniformly across the union of the data while minimizing the communication needed to run the protocol on the evolving data. At the same time, it is also necessary to make the protocol lightweight, by keeping the space and time costs low for each participant. In this article, we present communication-efficient protocols for continuously maintaining a sample (both with and without replacement) from\n            <jats:italic>k<\/jats:italic>\n            distributed streams. These apply to the case when we want a sample from the full streams, and to the sliding window cases of only the\n            <jats:italic>W<\/jats:italic>\n            most recent elements, or arrivals within the last\n            <jats:italic>w<\/jats:italic>\n            time units. We show that our protocols are optimal (up to logarithmic factors), not just in terms of the communication used, but also the time and space costs for each participant.\n          <\/jats:p>","DOI":"10.1145\/2160158.2160163","type":"journal-article","created":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T13:43:38Z","timestamp":1335879818000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["Continuous sampling from distributed streams"],"prefix":"10.1145","volume":"59","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"AT&amp;T Labs--Research, Florham Park, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[{"name":"MADALGO, Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634","author":"Babcock B.","unstructured":"Babcock , B. , Datar , M. , and Motwani , R . 2002. Sampling from a moving window over streaming data . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634 . Babcock, B., Datar, M., and Motwani, R. 2002. Sampling from a moving window over streaming data. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559818"},{"key":"e_1_2_1_5_1","volume-title":"The Discrepancy Method","author":"Chazelle B.","unstructured":"Chazelle , B. 2000. The Discrepancy Method . Cambridge University Press . Chazelle, B. 2000. The Discrepancy Method. Cambridge University Press."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases.","author":"Cormode G.","unstructured":"Cormode , G. and Garofalakis , M . 2005. Sketching streams through the net: Distributed approximate query tracking . In Proceedings of the International Conference on Very Large Data Bases. Cormode, G. and Garofalakis, M. 2005. Sketching streams through the net: Distributed approximate query tracking. In Proceedings of the International Conference on Very Large Data Bases."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Cormode G.","unstructured":"Cormode , G. , Muthukrishnan , S. , and Yi , K . 2008. Algorithms for distributed, functional monitoring . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Cormode, G., Muthukrishnan, S., and Yi, K. 2008. Algorithms for distributed, functional monitoring. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.173"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863992"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.11.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064116"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376657"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265544"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0065-y"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 541--550","author":"Gibbons P.","year":"2001","unstructured":"Gibbons , P. 2001 . Distinct sampling for highly-accurate answers to distinct values queries and event reports . In Proceedings of the International Conference on Very Large Data Bases. 541--550 . Gibbons, P. 2001. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In Proceedings of the International Conference on Very Large Data Bases. 541--550."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276334"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IEEE INFOCOMM.","author":"Huang L.","unstructured":"Huang , L. , Nguyen , X. , Garofalakis , M. , Hellerstein , J. , Joseph , A. D. , Jordan , M. , and Taft , N . 2007. Communication-efficient online detection of network-wide anomalies . In Proceedings of the IEEE INFOCOMM. Huang, L., Nguyen, X., Garofalakis, M., Hellerstein, J., Joseph, A. D., Jordan, M., and Taft, N. 2007. Communication-efficient online detection of network-wide anomalies. In Proceedings of the IEEE INFOCOMM."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_2_1_22_1","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming , Vol. 2 , Seminumerical Algorithms 2nd Ed. Addison-Wesley . Knuth, D. E. 1998. The Art of Computer Programming, Vol. 2, Seminumerical Algorithms 2nd Ed. Addison-Wesley."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1053724.1054115"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Muthukrishnan S.","year":"2003","unstructured":"Muthukrishnan , S. 2003 . Data streams: Algorithms and applications . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Muthukrishnan, S. 2003. Data streams: Algorithms and applications. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376958"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559820"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160158.2160163","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2160158.2160163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:50Z","timestamp":1750240490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160158.2160163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2160158.2160163"],"URL":"https:\/\/doi.org\/10.1145\/2160158.2160163","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}