Arbitrarily accurate approximation scheme for large-scale RFID cardinality estimation

One important issue of RFID applications is to estimate the cardinality of large-scale RFID tags in the interested region. From a practical perspective, we require: (i) the estimate can be arbitrarily accurate, and (ii) its time cost should be scalable with the tags size, regardless of the tags distribution. Existing solutions, however, either assume the use of hash functions with ideal random properties, or impose unacceptable computation/storage overhead for tags. More importantly, those approaches only give asymptotic results and fail to provide rigorous bounds for the rate of convergence. In this paper, we propose a new scheme, Arbitrarily Accurate Approximation (A³), to reliably estimate the number of tags with any desired accuracy. In particular, for a given requirement of (ε,δ), we show that A³ achieves O((log log n+ε^-2) log δ^-1) time efficiency. Results show that A³ significantly outperforms previous designs under various distributions of tags.