1
6.9kviews
Explain estimating moments with example.

Explain estimating moments with example.

1 Answer
0
1.2kviews


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.

Please log in to add an answer.