The Flajolet-Martin algorithm approximates the number of distinct elements in a data stream using a single pass, with space consumption that grows only logarithmically with the largest possible number of distinct elements. It was introduced by Philippe Flajolet and G. Nigel Martin in their 1984 paper Probabilistic Counting Algorithms for Data Base Applications, and was later refined in further papers including the LogLog and HyperLogLog cardinality-estimation techniques.
Connections
In Field
Source Wikipedia: Flajolet-Martin algorithm
Sources
Wikipedia: Flajolet-Martin algorithm
Lead section
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).
In Field: Algorithms and Complexity Theory, Lead sentence
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).
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.