Accurate and precise aggregation counting

摘要

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 to of the estimated value.