{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:10:27Z","timestamp":1767139827175,"version":"build-2238731810"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T00:00:00Z","timestamp":1544486400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T00:00:00Z","timestamp":1544486400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100012543","name":"Shanghai Science and Technology Development Foundation","doi-asserted-by":"publisher","award":["18YF1401200"],"award-info":[{"award-number":["18YF1401200"]}],"id":[{"id":"10.13039\/100012543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"crossref","award":["GRF-621413"],"award-info":[{"award-number":["GRF-621413"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"crossref","award":["GRF-16211614"],"award-info":[{"award-number":["GRF-16211614"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"crossref","award":["GRF-16200415"],"award-info":[{"award-number":["GRF-16200415"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61802069"],"award-info":[{"award-number":["61802069"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6,1]]},"DOI":"10.1007\/s00453-018-00531-y","type":"journal-article","created":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T04:36:23Z","timestamp":1544502983000},"page":"2222-2243","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2671-7483","authenticated-orcid":false,"given":"Zengfeng","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,11]]},"reference":[{"key":"531_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Cormode, G., Huang, Z., Phillips, J.M., Wei, Z., Yi, K.: Mergeable summaries. In: Proceedings of the ACM Symposium on Principles of Database Systems (2012)","DOI":"10.1145\/2213556.2213562"},{"key":"531_CR2","doi-asserted-by":"crossref","unstructured":"Arackaparambil, C., Brody, J., Chakrabarti, A.: Functional monitoring without monotonicity. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (2009)","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"531_CR3","doi-asserted-by":"crossref","unstructured":"Babcock, B., Olston, C.: Distributed top-k monitoring. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2003)","DOI":"10.1145\/872757.872764"},{"key":"531_CR4","unstructured":"Bar-Yossef, Z.: The complexity of massive data set computations. PhD thesis, University of California at Berkeley (2002)"},{"issue":"3\u20134","key":"531_CR5","first-page":"1088","volume":"62","author":"H-L Chan","year":"2011","unstructured":"Chan, H.-L., Lam, T.W., Lee, L.-K., Ting, H.-F.: Continuous monitoring of distributed data streams over a time-based sliding window. Algorithmica 62(3\u20134), 1088\u20131111 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"531_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2481528.2481530","volume":"42","author":"G Cormode","year":"2013","unstructured":"Cormode, G.: The continuous distributed monitoring model. ACM SIGMOD Rec. 42(1), 5\u201314 (2013)","journal-title":"ACM SIGMOD Rec."},{"key":"531_CR7","doi-asserted-by":"crossref","unstructured":"Cormode, G., Garofalakis, M., Muthukrishnan, S., Rastogi, R.: Holistic aggregates in a networked world: distributed tracking of approximate quantiles. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2005)","DOI":"10.1145\/1066157.1066161"},{"key":"531_CR8","doi-asserted-by":"crossref","unstructured":"Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. In: Proceedings of the International Conference on Very Large Data Bases (2008)","DOI":"10.14778\/1454159.1454225"},{"issue":"2","key":"531_CR9","doi-asserted-by":"publisher","first-page":"Article 21","DOI":"10.1145\/1921659.1921667","volume":"7","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. ACM Trans. Algorithms 7(2), Article 21 (2011). (Preliminary version in SODA\u201908)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"531_CR10","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/2160158.2160163","volume":"59","author":"G Cormode","year":"2012","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K., Zhang, Q.: Continuous sampling from distributed streams. J. ACM 59(2), 10 (2012). (Preliminary version in PODS\u201910)","journal-title":"J. ACM"},{"key":"531_CR11","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications. Wiley, New York (1968)"},{"key":"531_CR12","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B., Tirthapura, S.: Estimating simple functions on the union of data streams. In: Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (2001)","DOI":"10.1145\/378580.378687"},{"key":"531_CR13","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2001)","DOI":"10.1145\/375663.375670"},{"key":"531_CR14","doi-asserted-by":"crossref","unstructured":"Huang, Z., Wang, L., Yi, K., Liu, Y.: Sampling based algorithms for quantile computation in sensor networks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2011)","DOI":"10.1145\/1989323.1989401"},{"key":"531_CR15","doi-asserted-by":"crossref","unstructured":"Huang, Z., Yi, K., Liu, Y., Chen, G.: Optimal sampling algorithms for frequency estimation in distributed data. In: IEEE INFOCOM (2011)","DOI":"10.1109\/INFCOM.2011.5935005"},{"key":"531_CR16","doi-asserted-by":"crossref","unstructured":"Keralapura, R., Cormode, G., Ramamirtham, J.: Communication-efficient distributed monitoring of thresholded counts. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2006)","DOI":"10.1145\/1142473.1142507"},{"key":"531_CR17","unstructured":"Manjhi, A., Shkapenyuk, V., Dhamdhere, K., Olston, C.: Finding (recently) frequent items in distributed data streams. In: Proceedings of the IEEE International Conference on Data Engineering (2005)"},{"key":"531_CR18","doi-asserted-by":"crossref","unstructured":"Manku, G., Motwani, R.: Approximate frequency counts over data streams. In: Proceedings of the International Conference on Very Large Data Bases (2002)","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"issue":"3","key":"531_CR19","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1145\/1166074.1166084","volume":"31","author":"A Metwally","year":"2006","unstructured":"Metwally, A., Agrawal, D., Abbadi, A.: An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Trans. Database Syst. 31(3), 1095\u20131133 (2006)","journal-title":"ACM Trans. Database Syst."},{"key":"531_CR20","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J Misra","year":"1982","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Program. 2, 143\u2013152 (1982)","journal-title":"Sci. Comput. Program."},{"key":"531_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"531_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00446-008-0055-3","volume":"21","author":"B Patt-Shamir","year":"2008","unstructured":"Patt-Shamir, B., Shafrir, A.: Approximate distributed top-k queries. Distrib. Comput. 21(1), 1\u201322 (2008)","journal-title":"Distrib. Comput."},{"key":"531_CR23","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s00454-006-1269-4","volume":"36","author":"S Suri","year":"2006","unstructured":"Suri, S., Toth, C., Zhou, Y.: Range counting over multidimensional data streams. Discrete Comput. Geom. 36, 633\u2013655 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"531_CR24","doi-asserted-by":"crossref","unstructured":"Tirthapura, S., Woodruff, D.P.: Optimal random sampling from distributed streams revisited. In: Proceedings of the International Symposium on Distributed Computing (2011)","DOI":"10.1007\/978-3-642-24100-0_27"},{"key":"531_CR25","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."},{"key":"531_CR26","unstructured":"Woodruff, D.P.: Efficient and Private Distance Approximation in the Communication and Streaming Models. PhD thesis, Massachusetts Institute of Technology (2007)"},{"key":"531_CR27","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhang, Q.: Tight bounds for distributed functional monitoring. In: Proceedings of the ACM Symposium on Theory of Computing (2012)","DOI":"10.1145\/2213977.2214063"},{"key":"531_CR28","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: towards a unified measure of complexity. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"531_CR29","doi-asserted-by":"crossref","unstructured":"Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. In: Proceedings of the ACM Symposium on Principles of Database Systems (2009)","DOI":"10.1145\/1559795.1559820"}],"updated-by":[{"DOI":"10.1007\/s00453-020-00755-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T00:00:00Z","timestamp":1595894400000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00531-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00531-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00531-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,17]],"date-time":"2020-10-17T02:22:31Z","timestamp":1602901351000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00531-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,11]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6,1]]}},"alternative-id":["531"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00531-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,11]]},"assertion":[{"value":"27 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2020","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"After publication of the article [1] the authors have noticed that the funding information are not published in online and print version of the article. The omitted funding acknowledgement is given below.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}