Accurate and precise aggregation counting

作者：Preparata Franco P^*

来源：Journal of Computer and System Sciences, 2012, 78(1): 192-197.

DOI：10.1016/j.jcss.2011.02.002

• Aggregation
• Duplicate-insensitive
• Sensors networks

Aggregation counting is any procedure designed to solve the following problem: a number n of agents produces a fixed length binary message, and a central station produces an estimate of n from the bit-by-bit OR of the messages, which is therefore duplicate-insensitive. Such procedures are applicable to a situation where each of n independent sensors broadcasts the message to be used to estimate the count. A mathematically brilliant solution to this problem, due to Flajolet and Martin (1985) [1], is unfortunately affected by substantial bias and error. In this note we outline an alternative approach, which uses the Flajolet-Martin technique as a preparatory step and substantially reduces both error and bias. Specifically, the standard deviation of the count estimate drops from similar to 110% to similar to 20% of the estimated value.

• 出版日期2012-1