written 2.4 years ago by | • modified 2.4 years ago |
Explain estimating moments with example.
written 2.4 years ago by | • modified 2.4 years ago |
Explain estimating moments with example.
written 2.4 years ago by |
Estimating Moments :-
Estimating moments is a generalization of the problem of counting distinct elements in a stream. The problem, called computing "moments," involves the distribution of frequencies of different elements in the stream.
Suppose a stream consists of elements chosen from a universal set. Assume the universal set is ordered so we can speak of the $i^{th}$ element for any i.
Let $m_i$ be the number of occurrences of the $i^{th}$ element for any i. Then the $k^{th}$-order moment of the stream is the sum over all i of $(m_i)^k$
.
For example :-
The $0^{th}$ moment is the sum of 1 of each mi that is greater than 0 i.e., $0^{th}$ moment is a count of the number of distinct element in the stream.
The 1st moment is the sum of the $m_i$ ’s, which must be the length of the stream. Thus, first moments are especially easy to compute i.e., just count the length of the stream seen so far.
The second moment is the sum of the squares of the $m_i$’s. It is sometimes called the surprise number, since it measures how uneven the distribution of elements in the stream is.
To see the distinction, suppose we have a stream of length 100, in which eleven different elements appear. The most even distribution of these eleven elements would have one appearing 10 times and the other ten appearing 9 times each.
In this case, the surprise number is $10^2$ + 10 × $9^2$ = 910. At the other extreme, one of the eleven elements could appear 90 times and the other ten appear 1 time each. Then, the surprise number would be $90^2$ + 10 × 12 = 8110.