Our next topic regarding the processing of
streams is how we estimate the number of
dis, distinct elements in the stream
without storing everything we have seen.
The technique is known as the
Flajolet-Martin algorithm, we'll also see
a generalization of the technique
to computing moments of the stream,
which are essentially polynomials
in the number of occurrences of
each of the elements that
appear in the stream.
That sounds confusing but we'll make
the definition clear before long.
So I have a stream of elements chosen from
some universal set of possible elements.
We'll assume that there are n elements in
the set but n might be extremely large.
For example, the number of IPv6
addresses that could exist or
the set of urls crawled by Google.
All we want to do is know how many
different elements have appeared in
the stream.
If not too many elements
different elements have been
seen we can store all of them
with the index like a hash table.
So, we can tell an element arriving in
the stream is new or has been seen before.
That requires a great deal of space if,
either the number of different elements
is large or we are maintaining counts for
a large number of streams.
In our other case we can't maintain
what we need in main memory and
storing the setters or
sets on disk will slow us down too much.
Here are some example applications for
this problem.
We might be crawling a website and
want to know how many different
words appear at that site.
Curiosity isn't a great motivation but
doing this count might tell us
something about whether the site is an
artificial site constructed by a spammer.
When a spammer has to create a great
number of pages without doing much work,
they might use the same page over and
over.
Which would lower the number of distinct
words below one would expect for
the total size of the site.
Or they might pick random pages on
the web which would mean the site has no
coherent topic.
That would cause a number of distinct
words to be unexpectedly large.
Major websites like to advertise
the number of distinct users who
have visited the site or
used particular features of the site
in the most recent day, week or month.
Suppose now we are crawling the web,
we can't afford to follow links to every
page we visit, the job would never end.
So we have to cut off
the surge at some point.
There will be some pages we know exist
because we found links to them, but
we don't know what is on them or
what links exist on those pages.
So which pages should we crawl and
which should we not bother to crawl?
Well, a heuristic essentially a simple
approximation to the page rank,
it's the count the number end
links to each page we know about.
We then choose to crawl pages that
have the highest number of n links.
This is an example of an application where
the sets we are counting are rather small.
Most pages have few n links.
However, there are very many
pages that need to be counted, so
compressing the list of URLs with links
to a given page is a good thing to do.
We're going to explore he
case where there's the set or
sets we need to count are large enough
that we cannot conveniently maintain
the set's explicitly in mail memory,
we can't ever
get exact counts if we don't store
the entire set of elements seen.
So we'll look for the next best thing.
The way to estimate the count
in a way that converges to
the true answer as we allocate more
space to estimating each count.
The algorithm for estimating counts
that we will cover is called
the Flajolet-Martin algorithm
after the inventors.
So to start let's pick a hash function
that takes stream elements as its argument
and return a bit strings who's length is
sufficiently large that there are more
possible results of the hashing than there
are elements that might appear in the set.
That is, we need at least log in bits if
they are n elements in the universal set.
If a is a possible stream element,
define r of a to be the length of
the tail of the hash value, h of a.
That is the number of trailing
0's in the bit string, h of a.
Define capital R to be
the maximum value of r
of a that we have seen in the stream so
far.
That is, cap R is the largest
number of trailing 0's in
the hash function h applied to each of
the elements we've seen in the stream.
The estimate of the number of
distinct elements that we make from
these calculations is 2 to the R.
This may seem ridiculous because our
estimate is always a power of 2, and
it surely not every stream has a number of
distinct elements that is the power of 2,
but we're going to use
several hash functions and
get several different values of capital R.
By combining them in the right way,
we can in principle get any count as our
estimate of the number
of distinct elements.
There is intuition why this idea,
it gives a good estimate.
First notice that the number
of times an element repeats in
the stream has no effect
on the value of R,
because each time we hash the same value,
we get the same tail of 0s.
The value of r depends only on the number
of distinct elements in the stream.
The probability that the hash value for
any given element ends in i 0's
goes down exponentially with i.
So when we increase i by one we need to
double the number of different elements to
have a good chance of seeing i plus
one 0's at the end of some hash value.
That is why raising 2 to the power
equal to the longest tail of
0's is a reasonable estimate for
how many different elements we've seen.
The next slide tries to
make this idea formal.
First, the probability that the hash
value of an element ends in i or
more 0's is exactly 2 to the minus i.
That is, for
i equals 0, there is probability one
that the, the tail has at least zero 0s.
For i equals 1, there is half
a chance that the last bit is 0.
For i equals 2, the chance is a quarter
that the last two bits are 0, and so on.
So suppose the number of distinct
elements seen in the stream so far is m.
Here is the formula for
the probability that R,
the length of the longest
tail is at least i.
To see why, remember, 2 to the minus i is
the probability a tail has a least i 0's.
So 1 minus 2 to the minus i is the
probability that a tail does not end in
as many as i 0's.
And if we have m independent hashings
of different elements, we raise this
probability to the nth power to get the
probability that no tail is as long as i.
Finally, 1 minus that is the probability
that some element has a tail at
least as long as i.
To see why 2 to the r is generally
close to m, look at the formula for
the probability that R is at least i,
it's that.
We're only interested in
the case where i is large.
So 2 to the minus i is
tiny compared with 1.
I claim that this is approximately this,
where e is the base of natural logarithms.
The proof is similar to the one we
just gave regarding the throwing of
darts to targets, and
I'm not going to repeat it here [SOUND].
So the first case is where 2 to
the i is much greater than m.
We don't expect to find a tail as
large as i among m hash values.
But to see the math,
start with the formula for
the probability that R is at least i.
And again, that's, that's this.
Okay, since m times 2 to
the minus i is small when 2 to
the i is much bigger than m,
we can estimate this exponential,
that's again, that by the first
two terms of its Taylor expansion.
Remember that e to the x is 1 plus x
plus x squared over 2 factorial plus
x cubed over 3 factorial and so on.
If X is much less than 1 only
the first 2 terms are significant.
And that is what we
have done here where we
replaced the exponential by the first
two terms of, of the expansion.
But the 1's cancel and the plus of
course becomes a minus becomes a plus.
And that leaves us with m over 2 to the i.
And since we assume two of
the i's much bigger than an m,
the conclusion is that there
is very little probably that
R the largest value of i that will be
found among the tail lengths is such that
2 to the R our estimate of m
is much larger than m itself.
On the other hand, suppose 2 to
the i is much smaller than m, and
m times 2 to the minus i is large and
e raised to a large negative power,
that's this, is small.
So the probability of seeing a tail
of length at least i is close to 1.
Our conclusion is that 2 to
the R is almost always near m,
not much too big, and not much too small.
Unfortunately, reasoning about
the small probability of an over or
under estimate of m doesn't
tell the whole story.
The fact is that the expected
value of 2 to the R is infinite in
principle although the fact that there is
a upper limit on the length of a tail.
The number of bits in
the hash value that means
the expected value is not really infinite,
but some much too large number.
The argument for infinite expectation is
that we, as we move from R to R plus 1 and
probability of getting a tail
that large halves, but
the value of 2 to the R doubles.
As a result,
each value of R up to the maximum posi,
possible tail length contributes
the same amount to the expectation.
To deal with the infinite expected value,
we will need to use a large number of
independent hash functions and
those get many samples of values for R.
We need to do that anyway since one value,
even if it were a good estimate,
would not be exact, and
only by combining many estimates can we be
reasonably sure we're close to the truth.
So we need to combine
the samples of R that we get.
It's not obvious how we do that.
For example, if we take the average,
than one unusually large value
will distort the average too much.
And another option is to take the median.
The median lets us ignore really large or
small values, but
the trouble with medians is,
is that they are always one of the values
in the set whose median you're taking.
And this set is a collection
of powers of 2.
So the result would
always be a power of 2.
Here’s the way we combine averages and
medians to get an estimate that
is not biased to the high end and
which will converge to the exact
answer if we take enough samples.
That is,
we use enough different hash functions and
compute the maximum tail length for each.
Here is the way we combine averages and
medians to get an estimate that is
not biased to the high end, and
which will converge to the exact
answer if we take enough samples.
That is,
we use enough different hash functions and
compute the maximum tail length for each.
We're going to partition
the samples into small groups.
The group should be of size around log n,
at least log n where n is
the size of the universal set.
Then within a group we take the average.
And among all the averages of the groups
we take the median average, and
the result then will be an unbiased
estimate of m the number of
different elements in the stream.
I want to move on to a generalization of
the problem of counting distinct elements.
It's called estimating moments, and
the count of distinct elements will,
as we shall see, turn out to be
the 0th moment of the stream.
So as before, let's imagine we have
a stream whose elements are chosen from
a universal set of n elements.
And let the ith element occur,
m sub i times n stream so far.
And the kth moment of the stream is the
sum of all kth powers of the m's sub i's.
Here are the first three
moments of the stream and
the meanings, the 0th moment is the sum
of each m's of i raised to the 0th power.
0th power of anything except 0 is 1.
So we're actually counting the number of
distinct elements that have appeared so
far in the stream.
That is, the 0th moment is the problem
that the Flajolet-Martin algorithm solves.
The first moment is
the sum of the m sub i's.
That is, the sum of the counts of the
number of occurrences of all the elements.
That's just the length of the stream.
We can count the length of the stream
with a single counter that we
increment once per input.
This is easy.
Much easier than the other moments and
no estimation is needed.
The second moment, that is the sum
of the squares of the m's sub,
is is sometimes referred to
as the surprise number and
it gives a measure of how uneven the
distribution of elements in the stream is.
So, here's an example of
computing the second moment and
what the surprise is all about.
Well supposed that 100 elements have
arrived so far on the stream, and
that these elements are divided among
eleveron, eleven different values.
What would be unsurprising is that they
all appear at approximately the same
number of times.
The best we could do in that regard
is to have one appear 10 times and
the other is 9 times each.
The sum of these counts is 10
squared plus 10 times 9 squared,
which is 100 plus 10 times 81 and
is equal to 910.
That would be the lowest
possible surprise number for
stream with this number
of different elements.
Now what would be really surprising is if
one of the 11 numbers appeared 90 times,
and the other 10 appeared once each.
The sum of the squares
of the counts in this
case would be 90 squared plus n times 1
squared which is 8100 plus 10 or 8110.
That is the largest possible
surprise number in this situation.
I'm now going to introduce a technique
due to Alon, Matias, and Szegedy for
estimating a moment of a stream.
It works to compute any moment.
But we'll talk only
about the second moment.
The method involves keeping track of
the value of many different random
variables X as the stream grows.
Each random variable is analogous to
recording the maximum number of zeros in
the tail using a fixed hash function like
we did for the Flajolet-Martin algorithm.
And as for the Flajolet-Martin algorithm,
each random variable requires
storage of an integer.
Preferably in main memory.
So we're limited in how many variables
we can compute for each stream.
So let's see how we manage
one random variable.
We can manage as many as we can
afford in the same way of course.
Using different random numbers for each.
Okay.
So
let n be the length of the stream seen so
far.
N is going to grow as time goes on,
surely, but
right now it has some particular value.
For the random variable x, we need to pick
a random place in the stream to start so
that any starting point is
equally likely to be chosen.
This choice introduces the randomness.
If we have many random variables
they will be independent because for
each we choose a random starting
point independently of the others.
So let a be the element found
at the chosen starting point.
The value of random variable X is n,
the current stream length times twice
the number of occurrences of a we find in
the stream since the randomly chosen
starting point and then minus 1.
Notice that a surely occurs
at the time chosen but
may occur many times after that.
Occurrences before the chosen
time do not count.
An important point is that even
though X is defined this way you do
not have to change the value of
X each time n increases by 1.
We store n separately and
it could be used to compute the value of
each of the random variables if we needed.
What we actually store for
X is the element a, and
the count of occurrences of a since
the randomly chosen starting point.
This way when an input arrives at
the stream we can leave almost
all the variables unchanged.
We only have to change those for
which the element being counted
is the element that just arrived.
On this slide we're going to argue
that the expected value of a variable,
considering all the possible
starting times,
exactly equals the second
moment of the stream.
First, remember that the second moment
is the sum over all elements a of
the square of the number
of times a occurs.
Now, here's the formula for
the expected value of variable X.
There are n possible starting points,
each equally likely.
We'll average the value of X that is
computed for each of these starting times.
The 1 over n is for taking the average,
and everything else is the sum
over all possible times t of the value
that is computed when time t is chosen.
Remember that when t is
chosen as the start time,
the value of X is n times twice
the number of occurrences,,
that of that same element
in the stream from then on.
And then minus minus 1.
Okay, here we've rewritten the formula for
the expected value of x,
by grouping all the times from want to and
according to the symbol
a that is found there.
So we can sum over all symbols a.
Now the 1 over n and the n are constants
as far as the summation is concerned, so
we carry them over, and guess what.
They cancel.
Now the term for a given symbol a involves
several different times t in this string.
Each time will give a different value for
twice the number of a's minus 1.
The first term 1 represents
the time when the last a arrives.
Then the count will be 1.
That is twice the count is 2 and
then minus 1 leaves us with 1.
The 3 represents the next to
last time that a occurs, and
then the count will be 2.
Double it to make 4 and subtrap,
trip, subtract 1 to leave 3.
We continue like that for
each possible time an a appears and
we get all the odd integers in turn.
Finally, the largest count we
can get is when the time, t,
is the first time, a, appears.
Then the count will be m sub a,
the full number of times a appears,
we double it and subtract 1.
You can show that the sum
of all the odd integers up
to 2m sub i minus 1 is m by squared.
It's an easy induction and
I'm not going to do it here but for
example, if m of a is 4, then
1 plus 3 plus 5 plus 7 equals
16 which of course is 4 squared.
As I mentioned, we want not only
the correct expected value for a variable.
We want to know that as you use more and
more variables the average of
their estimates of the moment
will converge to the true value.
I'm just going to tell
you that's the case.
You combine them as for Flajolet-Martin
estimates group into small groups,
take the average of the groups and
then the median of the averages.
There's a small problem
we need to fix though.
We treated n as a constant but
in fact the stream is always growing,
and n is therefore a variable.
So, one consequence of n being
a variable is, is easy to fix.
In fact we mentioned it before,
we store n once an increment that
each time a new element arrives.
In the variable X,
we store only the count,
if we ever need the value of X,
we double the count subtract 1 and
then multiply the result
by the current value of n.
However the tricky part is how we
manage to keep the fixed number of
variables representing random choices
of positions with each position from
one to n equally likely, even as n grows.
That is, if we're keeping k random
variables, then whatever n is
we want each starting time to have been
selected with probability k over n.
So here's how we make sure that at
all times each of the N positions is
chosen with probability K over N.
The technique is called
reservoir sampling by the way.
To get started, each of the first k
positions in the stream is chosen.
That makes sense because
k over n is k over k or
1, before we reach the Kth
position we're not
really sampling since the best we can do
is to choose each position with certainty.
But now n is bigger than k so
not every position can be chosen.
So suppose the nth element arrives.
Prior to this there were n-1
positions in the stream, and
each was chosen with equal probability,
and that probability is k over n minus 1.
The nth element arrives.
We know the nth position has to be
chosen with probability k over n, so
let's generate a random number.
And do that for the the reason
we just arrived the position.
If the decision is not
to choose position n,
then no change is made to our
selection of k positions.
But, if you decide to pick position n then
select one of the current k positions at
random and
toss it from the set of positions.
We know the nth position has a k
over n chance of being chosen, but
how about the first n minus 1 positions?
Their probability can
be calculated as shown.
Okay.
There are two cases.
Either the n position was chosen or not.
If it is not chosen,
it is that chosen then with,
with probability n minus k over n.
Each of the first n minus 1 positions
as previously chosen with probability k
over n minus 1.
In the case where the nth
position is not chosen.
If some previous position had been chosen,
then it will still be chosen,
so we multiply by this factor.
But there's another term we have to add
to the probability is the product of
three factors.
First is the factor k over n,
representing the probability
that the nth position is chosen.
Now, in order for one of the fist n
minus 1 positions to remain chosen,
it must have been chosen previously.
That happens with probability k
over n minus 1, as we mentioned.
And it must not be thrown out.
It will not be thrown out with
probability k minus 1 over k.
Now I'll let you do the math, but
the expression does indeed simplify to k
over n so all n positions now have exactly
the same probability of being chosen.