Count-distinct problem: Difference between revisions

Revision as of 13:08, 1 June 2023

Revision as of 09:53, 27 October 2023

Line 5:

==Formal definition==

: '''Instance''': AConsider a stream of elements <math> x_1, x_2, \ldots, x_s </math> with repetitions, and an integer <math> m </math>. Let <math> n </math> bedenote the number of distinct elements in the stream, namelyrepresented as <math> n = |\left\{e_1, {x_1,x_2e_2, \ldots,x_s}\right e_n\}| </math>, and let these elements bewhere <math>n = |\left\{ {e_1, e_2, \ldots, e_n}\right\}|</math>. Here, <math>n</math> specifically refers to the count of unique elements in the stream, not the total number of elements in the original set.

: '''Objective''': Find an estimate <math> \widehat{n} </math> of <math> n </math> using only <math> m </math> storage units, where <math> m \ll n </math>.