Count-distinct problem: Difference between revisions

Revision as of 16:51, 30 May 2024

Revision as of 16:53, 30 May 2024

Line 5:

==Formal definition==

: '''Instance''': Consider a stream of elements <math>x_1, x_2, \ldots, x_s, \ldots </math> with repetitions. Let <math>n</math> denote the number of distinct elements in the stream, with the set of distinct elements represented as <math>\{e_1, e_2, \ldots, e_n\}</math>.

: '''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>.