Estimating Moments
In the context of stream processing, particularly in situations where you're
dealing with a sequence of data elements that come in one at a time (i.e., a
"stream"), the task of computing moments extends the idea of counting
distinct elements.
Instead of just knowing how many times a specific element appears in the
stream, you want to measure various statistical properties of the distribution
of frequencies across different elements in the stream.
Example:
Usage of Moments
It is also called as Surprise Number, since it measures how
uneven the distribution of elements in the stream is.
The Alon–Matias–Szegedy (AMS) Algorithm
Is an important algorithm in computer science, particularly in the context of
streaming algorithms and approximation algorithms.
It is designed for computing the second moment of a stream of data in a very
efficient way, using a probabilistic approach.
AMS Features:
1. It is a probabilistic algorithm that approximates the second moment of a
stream.
2. It takes a randomized approach to estimate the second moment efficiently
without explicitly storing all occurences of each element.
3. Uses a hashing technique to reduce the amount of information stored and
relies on probability to get an approximate answer.
Let us assume that a stream has a particular length 'n'
For all the elements mi in the stream, we compute some number of variables, X.
For each X:
1. save it as [Link]
2. Calculate an integer [Link], which is the value of the variable.
To determine the value of variable X, choose a position in the stream between 1
and n. Set [Link] to be the element found there and initialize [Link] to 1.
As the stream is read, add 1 to [Link] everytime another occurence of
[Link] is encountered.
Stream: a, b, c, b, d, a, c, d, a, b, d, c, a, a, b
n = 15
'a' appears 5 times
'b' appears 4 times
'c' appears 3 times
'd' appears 3 times
Second moment =
Keep 3 variables:
X1, X2 and X3
Pick at "random" 3rd, 8th and 13th positions to define these variables. (or
randomly pick)
a, b, c, b, d, a, c, d, a, b, d, c, a, a, b
At the 3rd position, we get element 'c' so set
X1. element = c and [Link] = 1
At position 4, nothing happens, since we have 'b' there, so no need to change
[Link]. Nothing happens at position 5 and 6.
a, b, c, b, d, a, c, d, a, b, d, c, a, a, b
At the 7th position, we get element 'c' again, so set
[Link] = 2
At position 8, we have 'd' there, so set
[Link] = d [Link] = 1
Positions 9 and 10 hold element 'a' and 'b', that do not affect X1 or X2
Position 11 holds element 'd', so [Link] =2
Position 12 holds element 'c', so [Link] = 3
a, b, c, b, d, a, c, d, a, b, d, c, a, a, b
At the 13th position, we get element 'a', so set
[Link] = a [Link] = 1
At position 14th, we have 'a' there, so set
[Link] = 2
Positions 15th, nothing happens.
So final values are [Link] = 3, [Link] = 2 and [Link] = 2.
From X1 we can estimate 15 x (2 x 3 -1) = 75
X2 and X3 have value = 2
Estimate it is 15 x (2 x 2 -1) = 45
Take average of the 3 estimates : (75 + 45 + 45) /3 = 55
Original computed moment is 59, so we have got a fairly close
approximation
Higher Order Moments using The AMS Algorithm:
To estimate the kth moments, k >2
Use the formula n(2v-1) where
n - length of the stream
v - count of the occurences of an element
(2v-1) is the difference between v^2 and (v-1)^2
To calculate third moment replace (2v-1) by v^3 - (v-1)^3 = 3v^2 - 3V +1
Solve using AMS.
Randomly sample 3
elements (A, B & C) from
2nd position.