  The amount of data coming from different sources such as IoT-sensors, social
networks, cellular networks, has increased exponentially during the last few
years. Probabilistic Data Structures (PDS) are efficient alternatives to
deterministic data structures suitable for large data processing and streaming
applications. They are mainly used for approximate membership queries,
frequency count, cardinality estimation and similarity research. Finding the
number of distinct elements in a large dataset or in streaming data is an
active research area. In this work, we show that usual methods based on Bloom
filters for this kind of cardinality estimation are relatively accurate on
average but have a high variance. Therefore, reducing this variance is
interesting to obtain accurate statistics. We propose a probabilistic approach
to estimate more accurately the cardinality of a Bloom filter based on its
parameters, i.e., number of hash functions $k$, size $m$, and a counter $s$
which is incremented whenever an element is not in the filter (i.e., when the
result of the membership query for this element is negative). The value of the
counter can never be larger than the exact cardinality due to the Bloom
filter's nature, but hash collisions can cause it to underestimate it. This
creates a counting error that we estimate accurately, in-stream, along with its
standard deviation. We also discuss a way to optimize the parameters of a Bloom
filter based on its counting error. We evaluate our approach with synthetic
data created from an analysis of a real mobility dataset provided by a mobile
network operator in the form of displacement matrices computed from mobile
phone records. The approach proposed here performs at least as well on average
and has a much lower variance (about 6 to 7 times less) than state of the art
methods.
