Flajolet–Martin algorithm

The Flajolet–Martin algorithm is an algorithm for approximating the number of distinct elements in a stream with a single pass and space-consumption logarithmic in the maximal number of possible distinct elements in the stream (the count-distinct problem). The algorithm was introduced by Philippe Flajolet and G. Nigel Martin in their 1984 article "Probabilistic Counting Algorithms for Data Base Applications".[1] Later it has been refined in "LogLog counting of large cardinalities" by Marianne Durand and Philippe Flajolet,[2] and "HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet et al.[3]

In their 2010 article "An optimal algorithm for the distinct elements problem",[4] Daniel M. Kane, Jelani Nelson and David P. Woodruff give an improved algorithm, which uses nearly optimal space and has optimal O(1) update and reporting times.

The algorithm

edit

Assume that we are given a hash function   that maps input   to integers in the range  , and where the outputs are sufficiently uniformly distributed. Note that the set of integers from 0 to   corresponds to the set of binary strings of length  . For any non-negative integer  , define   to be the  -th bit in the binary representation of  , such that:

 

We then define a function   that outputs the position of the least-significant set bit in the binary representation of  , and   if no such set bit can be found as all bits are zero:

 

Note that with the above definition we are using 0-indexing for the positions, starting from the least significant bit. For example,  , since the least significant bit is a 1 (0th position), and  , since the least significant set bit is at the 3rd position. At this point, note that under the assumption that the output of our hash function is uniformly distributed, then the probability of observing a hash output ending with   (a one, followed by   zeroes) is  , since this corresponds to flipping   heads and then a tail with a fair coin.

Now the Flajolet–Martin algorithm for estimating the cardinality of a multiset   is as follows:

  1. Initialize a bit-vector BITMAP to be of length   and contain all 0s.
  2. For each element   in  :
    1. Calculate the index  .
    2. Set  .
  3. Let   denote the smallest index   such that  .
  4. Estimate the cardinality of   as  , where  .

The idea is that if   is the number of distinct elements in the multiset  , then   is accessed approximately   times,   is accessed approximately   times and so on. Consequently, if  , then   is almost certainly 0, and if  , then   is almost certainly 1. If  , then   can be expected to be either 1 or 0.

The correction factor   is found by calculations, which can be found in the original article.

Improving accuracy

edit

A problem with the Flajolet–Martin algorithm in the above form is that the results vary significantly. A common solution has been to run the algorithm multiple times with   different hash functions and combine the results from the different runs. One idea is to take the mean of the   results together from each hash function, obtaining a single estimate of the cardinality. The problem with this is that averaging is very susceptible to outliers (which are likely here). A different idea is to use the median, which is less prone to be influences by outliers. The problem with this is that the results can only take form  , where   is integer. A common solution is to combine both the mean and the median: Create   hash functions and split them into   distinct groups (each of size  ). Within each group use the mean for aggregating together the   results, and finally take the median of the   group estimates as the final estimate.[5]

The 2007 HyperLogLog algorithm splits the multiset into subsets and estimates their cardinalities, then it uses the harmonic mean to combine them into an estimate for the original cardinality.[3]

See also

edit

References

edit
  1. ^ Flajolet, Philippe; Martin, G. Nigel (1985). "Probabilistic counting algorithms for data base applications" (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8. Retrieved 2016-12-11.
  2. ^ Durand, Marianne; Flajolet, Philippe (2003). "Loglog Counting of Large Cardinalities" (PDF). Algorithms - ESA 2003. Lecture Notes in Computer Science. Vol. 2832. p. 605. doi:10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Retrieved 2016-12-11.
  3. ^ a b Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm" (PDF). Discrete Mathematics and Theoretical Computer Science Proceedings. AH. Nancy, France: 127–146. CiteSeerX 10.1.1.76.4286. Retrieved 2016-12-11.
  4. ^ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "An optimal algorithm for the distinct elements problem" (PDF). Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data - PODS '10. p. 41. doi:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. S2CID 10006932. Retrieved 2016-12-11.
  5. ^ Leskovec, Rajaraman, Ullman (2014). Mining of Massive Datasets (2nd ed.). Cambridge University Press. p. 144. Retrieved 2022-05-30.{{cite book}}: CS1 maint: multiple names: authors list (link)

Additional sources

edit