Explain Flajolet Martin Algorithm with example.

65kviews

written 5.1 years ago by

swatisharma • 1.3k

modified 2.5 years ago by

besharateif739 • 10

big data analytics

ADD COMMENT EDIT

Thanks for excellent explanation. But I have one question. When x=4, Hash function's output is 5 and there are 5 zeros in tail. Therefor our max R is 5 and distinct elements will be 32. But in input stream we have 4 distinct elements. I think, we should not count all-zero element. May you explain more, please?

2.5 years ago by besharateif739 • 10

2 Answers

7.6kviews

written 5.1 years ago by

yashbeer ★ 11k

Flajolet-Martin algorithm approximates the number of unique objects in a stream or a database in one pass. If the stream contains n elements with m of them unique, this algorithm runs in $O(n)$ time and needs $O(log(m))$ memory.

Algorithm:

Create a bit vector (bit array) of sufficient length L, …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT

3.3kviews

written 5.1 years ago by

teamques10 ★ 65k

We may want to know how many different elements have appeared in the stream.
For example, we wish to know how many distinct users visited the website till now or in last 2 hours.
If no of distinct elements required to process many streams then keeping data in main memory …

Create a free account to keep reading this post.

and 4 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.