{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:14Z","timestamp":1750306034435,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,3,29]],"date-time":"2018-03-29T00:00:00Z","timestamp":1522281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish Ministry of Science and Higher Education","award":["0402\/0206\/16"],"award-info":[{"award-number":["0402\/0206\/16"]}]},{"DOI":"10.13039\/501100004281","name":"National Science Centre Poland","doi-asserted-by":"crossref","award":["2013\/09\/B\/ST6\/02258"],"award-info":[{"award-number":["2013\/09\/B\/ST6\/02258"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2018,5,31]]},"abstract":"<jats:p>We propose a new algorithm for the classical averaging problem for distributed wireless sensors networks. This subject has been studied extensively and there are many clever algorithms in the literature. These algorithms are based on the idea of local exchange of information. They behave well in dense networks (e.g., in networks whose connections form a complete graph), but their convergence to the real average is very slow in linear or cyclic graphs.<\/jats:p>\n          <jats:p>Our solution is different. In order to calculate the average, we first build an approximate histogram of observed data; then, from this histogram, we estimate the average. In our solution, we use the extreme propagation technique and probabilistic counters. It allows us to find the approximation of the average of a set of measurements done by sensor network with arbitrary precision, controlled by two parameters. Our method requires O(D) rounds, where D is the diameter of the network. We study the message complexity of this algorithm and show that it is of order O(log n) for each node, where n is the size of the network.<\/jats:p>","DOI":"10.1145\/3177922","type":"journal-article","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T12:19:12Z","timestamp":1522412352000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Average Counting via Approximate Histograms"],"prefix":"10.1145","volume":"14","author":[{"given":"Jacek","family":"Cicho\u0144","sequence":"first","affiliation":[{"name":"Faculty of Fundamental Problems of Technology, Wroc\u0142aw University of Science and Technology Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karol","family":"Gotfryd","sequence":"additional","affiliation":[{"name":"Faculty of Fundamental Problems of Technology, Wroc\u0142aw University of Science and Technology Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03342028"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0288-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016247"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAS.2009.31"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.209"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2009.4960420"},{"volume-title":"Probability and Measure (anniversary ed.)","author":"Billingsley Patrick","key":"e_1_2_1_7_1","unstructured":"Patrick Billingsley . 2012. Probability and Measure (anniversary ed.) . Wiley, Hoboken , NJ. Patrick Billingsley. 2012. Probability and Measure (anniversary ed.). Wiley, Hoboken, NJ."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34707-8_15"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30823-9_8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LADC.2009.19"},{"volume-title":"Handbook of Data Visualization","author":"Hrdle Wolfgang","key":"e_1_2_1_12_1","unstructured":"Chun-houh Chen, Wolfgang Hrdle , and Antony Unwin . 2008. Handbook of Data Visualization (Springer Handbooks of Computational Statistics) (1 ed.). Springer-Verlag TELOS , Santa Clara, CA. Chun-houh Chen, Wolfgang Hrdle, and Antony Unwin. 2008. Handbook of Data Visualization (Springer Handbooks of Computational Statistics) (1 ed.). Springer-Verlag TELOS, Santa Clara, CA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873736"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMS.2016.40"},{"key":"e_1_2_1_15_1","volume-title":"WCNC 2012","author":"Cicho\u0144 Jacek","year":"2012","unstructured":"Jacek Cicho\u0144 , Jakub Lemiesz , Wojciech Szpankowski , and Marcin Zawada . 2012 b. Two-phase cardinality estimation protocols for sensor networks with provable precision. In 2 Wireless Communications and Networking Conference , WCNC 2012 , Paris, France , April 1-4, 2012. IEEE, 2009--2013. Jacek Cicho\u0144, Jakub Lemiesz, Wojciech Szpankowski, and Marcin Zawada. 2012b. Two-phase cardinality estimation protocols for sensor networks with provable precision. In 2 Wireless Communications and Networking Conference, WCNC 2012, Paris, France, April 1-4, 2012. IEEE, 2009--2013."},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"ADHOC-NOW, Hannes Frey, Xu Li, and Stefan R\u00fchrup (Eds.)","author":"Cicho\u0144 Jacek","unstructured":"Jacek Cicho\u0144 , Jakub Lemiesz , and Marcin Zawada . 2011. On Cardinality Estimation Protocols for Wireless Sensor Networks . In ADHOC-NOW, Hannes Frey, Xu Li, and Stefan R\u00fchrup (Eds.) , Lecture Notes in Computer Science , Vol. 6811 . Springer , Berlin , 322--331. Jacek Cicho\u0144, Jakub Lemiesz, and Marcin Zawada. 2011. On Cardinality Estimation Protocols for Wireless Sensor Networks. In ADHOC-NOW, Hannes Frey, Xu Li, and Stefan R\u00fchrup (Eds.), Lecture Notes in Computer Science, Vol. 6811. Springer, Berlin, 322--331."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31638-8_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2011.81"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978068"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.908946"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934993"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095207"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2013.01.006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095245"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855641.1855654"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.056"},{"key":"e_1_2_1_28_1","volume-title":"28th International Symposium on Distributed Computing (DISC\u201914)","author":"Holzer Stephan","year":"2014","unstructured":"Stephan Holzer , David Peleg , Liam Roditty , and Roger Wattenhofer . 2014 . Brief Announcement: Distributed 3\/2-Approximation of the Diameter . In 28th International Symposium on Distributed Computing (DISC\u201914) , Austin, Texas, USA. Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. 2014. Brief Announcement: Distributed 3\/2-Approximation of the Diameter. In 28th International Symposium on Distributed Computing (DISC\u201914), Austin, Texas, USA."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2012.6288575"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.02.003"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2007.01.002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946317"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3027488"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031525"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_58"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2010.16"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/66.3.605"},{"volume-title":"Expansions and Asymptotics for Statistics","author":"Small Christopher G.","key":"e_1_2_1_41_1","unstructured":"Christopher G. Small . 2010. Expansions and Asymptotics for Statistics . CRC Press , Boca Raton, FL . https:\/\/books.google.co.uk\/books?id&equals;uXexXLoZnZAC Christopher G. Small. 2010. Expansions and Asymptotics for Statistics. CRC Press, Boca Raton, FL. https:\/\/books.google.co.uk\/books?id&equals;uXexXLoZnZAC"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177922","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3177922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,29]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,5,31]]}},"alternative-id":["10.1145\/3177922"],"URL":"https:\/\/doi.org\/10.1145\/3177922","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2018,3,29]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}