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". Later it has been refined in "LogLog counting of large cardinalities" by Marianne Durand and Philippe Flajolet, and "HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet et al. In their 2010 article "An optimal algorithm for the distinct elements problem", 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. 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: Initialize a bit-vector BITMAP to be of length and contain all 0s.