{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:59:34Z","timestamp":1777615174366,"version":"3.51.4"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            Consider the following problem: We have\n            <jats:italic>k<\/jats:italic>\n            players each receiving a stream of items, and communicating with a central coordinator. Let the multiset of items received by player\n            <jats:italic>i<\/jats:italic>\n            up until time\n            <jats:italic>t<\/jats:italic>\n            be\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>t<\/jats:italic>\n            ). The coordinator's task is to monitor a given function\n            <jats:italic>f<\/jats:italic>\n            computed over the union of the inputs \u222a\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>t<\/jats:italic>\n            ),\n            <jats:italic>continuously<\/jats:italic>\n            at all times\n            <jats:italic>t<\/jats:italic>\n            . The goal is to minimize the number of bits communicated between the players and the coordinator. Of interest is the approximate version where the coordinator outputs 1 if\n            <jats:italic>f<\/jats:italic>\n            \u2265 \u03c4 and 0 if\n            <jats:italic>f<\/jats:italic>\n            \u2264 (1\u2212\u03f5)\u03c4. This defines the (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            ,\u03c4,\u03f5)\n            <jats:italic>distributed functional monitoring<\/jats:italic>\n            problem. Functional monitoring problems are fundamental in distributed systems, in particular sensor networks, where we must minimize communication; they also connect to the well-studied streaming model and communication complexity. Yet few formal bounds are known for functional monitoring.\n          <\/jats:p>\n          <jats:p>\n            We give upper and lower bounds for the (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            ,\u03c4,\u03f5) problem for some of the basic\n            <jats:italic>f<\/jats:italic>\n            's. In particular, we study the frequency moments\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>\n              <jats:italic>p<\/jats:italic>\n            <\/jats:sub>\n            for\n            <jats:italic>p<\/jats:italic>\n            =0,1,2. For\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            and\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , we obtain monitoring algorithms with cost almost the same as algorithms that compute the function for a single instance of time. However, for\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            the monitoring problem seems to be much harder than computing the function for a single time instance. We give a carefully constructed multiround algorithm that uses \u201csketch summaries\u201d at multiple levels of details and solves the (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ,\u03c4,\u03f5) problem with communication\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\u03f5 +\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            \/\u03f5\n            <jats:sup>3<\/jats:sup>\n            ). Our algorithmic techniques are likely to be useful for other functional monitoring problems as well.\n          <\/jats:p>","DOI":"10.1145\/1921659.1921667","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T12:01:30Z","timestamp":1301400090000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Algorithms for distributed functional monitoring"],"prefix":"10.1145","volume":"7","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"AT&amp;T Labs, 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":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,31]]},"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.1007\/978-3-642-02927-1_10"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872764"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Workshop on Randomization and Approximation Techniques(1) RANDOM.","author":"Bar-Yossef Z.","unstructured":"Bar-Yossef , Z. , Jayram , T. S. , Kumar , R. , Sivakumar , D. , and Trevisan , L . 2002. Counting distinct elements in a data stream . In Proceedings of the International Workshop on Randomization and Approximation Techniques(1) RANDOM. Bar-Yossef, Z., Jayram, T. S., Kumar, R., Sivakumar, D., and Trevisan, L. 2002. Counting distinct elements in a data stream. In Proceedings of the International Workshop on Randomization and Approximation Techniques(1) RANDOM."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109634"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Very Large Databases.","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 Databases. Cormode, G. and Garofalakis, M. 2005. Sketching streams through the net: Distributed approximate query tracking. In Proceedings of the International Conference on Very Large Databases."},{"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","volume-title":"Proceedings of the IEEE International Conference on Data Engineering.","author":"Cormode G.","unstructured":"Cormode , G. , Muthukrishnan , S. , and Zhuang , W . 2007. Conquering the divide: Continuous clustering of distributed data streams . In Proceedings of the IEEE International Conference on Data Engineering. Cormode, G., Muthukrishnan, S., and Zhuang, W. 2007. Conquering the divide: Continuous clustering of distributed data streams. In Proceedings of the IEEE International Conference on Data Engineering."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Very Large Databases.","author":"Das A.","unstructured":"Das , A. , Ganguly , S. , Garofalakis , M. , and Rastogi , R . 2004. Distributed set-expression cardinality estimation . In Proceedings of the International Conference on Very Large Databases. Das, A., Ganguly, S., Garofalakis, M., and Rastogi, R. 2004. Distributed set-expression cardinality estimation. In Proceedings of the International Conference on Very Large Databases."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the IEEE Annual Joint Conference of the Computer and Communication Societies (InfoCom).","author":"Dilman M.","unstructured":"Dilman , M. and Raz , D . 2001. Efficient reactive monitoring . In Proceedings of the IEEE Annual Joint Conference of the Computer and Communication Societies (InfoCom). Dilman, M. and Raz, D. 2001. Efficient reactive monitoring. In Proceedings of the IEEE Annual Joint Conference of the Computer and Communication Societies (InfoCom)."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the IEEE Annual Joint Conference of the Computer and Communication Societies (InfoCom).","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 Annual Joint Conference of the Computer and Communication Societies (InfoCom). 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 Annual Joint Conference of the Computer and Communication Societies (InfoCom)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 3rd Workshop on Hot Topics in Networks (Hotnets).","author":"Jain A.","unstructured":"Jain , A. , Hellerstein , J. , Ratnasamy , S. , and Wetherall , D . 2004. A wakeup call for internet monitoring systems: The case for distributed triggers . In Proceedings of the 3rd Workshop on Hot Topics in Networks (Hotnets). Jain, A., Hellerstein, J., Ratnasamy, S., and Wetherall, D. 2004. A wakeup call for internet monitoring systems: The case for distributed triggers. In Proceedings of the 3rd Workshop on Hot Topics in Networks (Hotnets)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/605397.605408"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142507"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061322"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872825"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Yi K.","unstructured":"Yi , K. and Zhang , Q . 2009a. Multi-Dimensional online tracking . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Yi, K. and Zhang, Q. 2009a. Multi-Dimensional online tracking. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559820"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921667","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921659.1921667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1921659.1921667"],"URL":"https:\/\/doi.org\/10.1145\/1921659.1921667","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2008-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}