{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T15:42:53Z","timestamp":1783784573655,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006505","name":"Engineer Research and Development Center","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006505","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-08-1-0452"],"award-info":[{"award-number":["W911NF-08-1-0452"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["GRF-621413"],"award-info":[{"award-number":["GRF-621413"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-09-40671, CCF-10-12254, and CCF-11-61359"],"award-info":[{"award-number":["CCF-09-40671, CCF-10-12254, and CCF-11-61359"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            We study the\n            <jats:italic>mergeability<\/jats:italic>\n            of data summaries. Informally speaking, mergeability requires that, given two summaries on two datasets, there is a way to merge the two summaries into a single summary on the two datasets combined together, while preserving the error and size guarantees. This property means that the summaries can be merged in a way akin to other algebraic operators such as sum and max, which is especially useful for computing summaries on massive distributed data. Several data summaries are trivially mergeable by construction, most notably all the\n            <jats:italic>sketches<\/jats:italic>\n            that are linear functions of the datasets. But some other fundamental ones, like those for heavy hitters and quantiles, are not (known to be) mergeable. In this article, we demonstrate that these summaries are indeed mergeable or can be made mergeable after appropriate modifications. Specifically, we show that for \u03b5-approximate heavy hitters, there is a deterministic mergeable summary of size\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03b5); for \u03b5-approximate quantiles, there is a deterministic summary of size\n            <jats:italic>O<\/jats:italic>\n            ((1\/\u03b5) log(\u03b5\n            <jats:italic>n<\/jats:italic>\n            )) that has a restricted form of mergeability, and a randomized one of size\n            <jats:italic>O<\/jats:italic>\n            ((1\/\u03b5) log\n            <jats:sup>3\/2<\/jats:sup>\n            (1\/\u03b5)) with full mergeability. We also extend our results to geometric summaries such as \u03b5-approximations which permit approximate multidimensional range counting queries. While most of the results in this article are theoretical in nature, some of the algorithms are actually very simple and even perform better than the previously best known algorithms, which we demonstrate through experiments in a simulated sensor network.\n          <\/jats:p>\n          <jats:p>\n            We also achieve two results of independent interest: (1) we provide the best known randomized streaming bound for \u03b5-approximate quantiles that depends only on \u03b5, of size\n            <jats:italic>O<\/jats:italic>\n            ((1\/\u03b5) log\n            <jats:sup>3\/2<\/jats:sup>\n            (1\/\u03b5)), and (2) we demonstrate that the MG and the SpaceSaving summaries for heavy hitters are isomorphic.\n          <\/jats:p>","DOI":"10.1145\/2500128","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":102,"title":["Mergeable summaries"],"prefix":"10.1145","volume":"38","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Tsinghua University and Hong Kong University of Science and Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0546-7"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RandOM'02)","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 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RandOM'02) . 1--10. 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 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RandOM'02). 1--10."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_2_1_8_1","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"Chazelle B.","unstructured":"Chazelle , B. 2000. The Discrepancy Method: Randomness and Complexity . Cambridge University Press . Chazelle, B. 2000. The Discrepancy Method: Randomness and Complexity. Cambridge University Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0060"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases.","author":"Cormode G.","unstructured":"Cormode , G. and Hadjieleftheriou , M . 2008b. Finding frequent items in data streams . In Proceedings of the International Conference on Very Large Data Bases. Cormode, G. and Hadjieleftheriou, M. 2008b. Finding frequent items in data streams. In Proceedings of the International Conference on Very Large Data Bases."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Feldman J.","unstructured":"Feldman , J. , Muthukrishnan , S. , Sidiropoulos , A. , Stein , C. , and Svitkina , Z . 2008. On distributing symmetric streaming computations . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Feldman, J., Muthukrishnan, S., Sidiropoulos, A., Stein, C., and Svitkina, Z. 2008. On distributing symmetric streaming computations. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases.","author":"Gilbert A. C.","unstructured":"Gilbert , A. C. , Kotidis , Y. , Muthukrishnan , S. , and Strauss , M. J . 2002. How to summarize the universe: Dynamic maintenance of quantiles . In Proceedings of the International Conference on Very Large Data Bases. Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. J. 2002. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the International Conference on Very Large Data Bases."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055597"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514926"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796588"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989401"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993735"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.14"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.23"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066191"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1053724.1054115"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276342"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103470"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574066"},{"key":"e_1_2_1_32_1","volume-title":"Geometric Discrepancy: An Illustrated Guide","author":"Matousek J.","year":"2010","unstructured":"Matousek , J. 2010 . Geometric Discrepancy: An Illustrated Guide , vol. 18 . Springer http:\/\/bookshelf.theopensourcelibrary.org\/2010_CharlesUniversity_GeometricDiscrepancy.pdf. Matousek, J. 2010. Geometric Discrepancy: An Illustrated Guide, vol. 18. Springer http:\/\/bookshelf.theopensourcelibrary.org\/2010_CharlesUniversity_GeometricDiscrepancy.pdf."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 16th International Workshop on Randomization and Computation (RandOM'12)","author":"Nelson J.","unstructured":"Nelson , J. , Nguyen , H. L. , and Woodruff , D. P . 2012. On deterministic sketching and streaming for sparse recovery and norm estimation . In Proceedings of the 16th International Workshop on Randomization and Computation (RandOM'12) . Nelson, J., Nguyen, H. L., and Woodruff, D. P. 2012. On deterministic sketching and streaming for sparse recovery and norm estimation. In Proceedings of the 16th International Workshop on Randomization and Computation (RandOM'12)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_37"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1269-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988847"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500128","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2500128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:31Z","timestamp":1750232071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2500128"],"URL":"https:\/\/doi.org\/10.1145\/2500128","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}