If the dataless stream is arriving
too rapidly, we may not want to or
need to look at every stream element.
Perhaps we can get by with just a small
sample of the values in he stream.
But we have to worry about two things.
First, the sample better be unbiased.
The second, the sampling process must
deserve the answer to the query, or
queries we want to ask about the data.
Unbaised sampling is not hard but cala,
carelessly choosing how we sample
can distort the result of queries.
So, after a discussion of the pitfalls,
we'll see a method that preserves
the answer to a given query.
Introducing only the noise that comes from
the fact that we are sampling at random.
Let's take up an example.
Google has a stream of search
queries coming in at all times.
We might want to know, what fraction of
search queries received over a period,
such as a month, are unique?
That is, there's only one occurrence of
that search query in the entire month.
Many questions about the stream can
be answered by sampling the stream.
Suppose to be concrete that we randomly
select 1/10th of the queries to
be examined.
For example if we wanted to know,
what fraction of the search
queries were single word queries?
We could compute that fraction for the,
for the sample and
be pretty sure that it was very close.
To the fraction for the stream as a whole.
That is, over a month, a 1/10th sample
would be a billion queries or more.
Statistically, if those queries
are selected at random,
the deviation from the true
answer will be miniscule.
However, we want the fraction
of unique queries.
And this query cannot
be answered correctly,
from a random sample of the stream.
In fact, as we will see on the next slide,
there's not enough information to
deduce the fraction, for the entire
stream from the fraction with the sample.
Let's do the math of
the matter of unique queries.
First, we know that there will be
in the sample very close to 10%,
of the query occurrences
of the original stream.
The problem is that the probability of
a given query appearing to be unique in
the sample,
gets distorted because of the sample.
First, suppose the query is
unique in the stream as a whole.
It has a one tenth chance of
being selected for the sample.
That's fine.
It says that the fraction of
truly unique queries that make it
into the sample is the same as for
the whole stream.
If we could only count the truly
unique queries in the sample,
we would get the right answer.
However, suppose a search query appears
exactly twice in the whole stream?
The chance that the first occurrence
will be selected for the sample is 10%,
and the chance that the second
occurrence will not be selected is 90%.
Multiply those and
we have a 9% chance with this query
occurrence being unique in the sample.
Moreover the first occurrence could not be
selected, but the second is selected, and
that's another 9% chance of
a query that really occurs twice
looking unique in the sample.
That's a total of 18%.
I'll let you do the calculation,
but a query that
appears in the stream 3 times has a 24.3%
chance of looking unique in the sample.
And in fact, any query, no matter how many
times it appears in the original stream,
has at least a small chance of
looking unique in the sample.
So when we count the number of
unique queries in the sample,
it will be an overestimate of
the true fraction of unique queries,
very possibly a substantial overestimate.
In fact, there could be no
unique queries in the original.
And yet, many in the sample.
And worse, we just don't know
from the sample whether,
we're looking at truly unique queries,
or not.
We may as well toss out the data,
and start over again.
If you think about it,
the problem was that we assumed we
flipped a ten sided coin every time
a new element arrived on the stream.
The consequence is that when a query
occurs at several positions in the stream,
we decided independently whether or
not to add each one to the sample.
That isn't what we want.
We want to pick one tenth
of the search queries,
not one tenth of the instances of
search queries in the stream, and
we can make the random decision
the first time we see each search query.
If kept the table of our decision for
each search query we've ever seen,
then each time the query appears,
we could look it up in the table.
If we fa, if found the, the, we do the
same we did with the first occurrence of
that query add it to the sample or not.
But, if we didn't find the query in
the table we'd flip that ten sided coin to
decide what to do with it.
And we called the query and
the outcome in the table.
That's kind of unappetizing.
It will be hard to manage the table, and
there is a lookup with
each stream element.
Fortunately, there's a much simpler
way to get the same effect,
without storing anything.
Okay, let's pick a hash function from
search queries to 10 buckets, 0 through 9.
When the search query arrives hash it.
If it goes to bucket 0
then add it to the sample.
And if it goes to any of the 9 other
buckets, do not add it to the sample.
The cool thing about this approach
is that, all occurrences of the same
query hash to the same bucket, because
the same hash function is always applied.
As a result, we don't need to know whether
the search query that just arrived
has been seen before.
And we don't need to
know what action we took.
We can be sure that if
it did appear before,
we'll do the same thing
now that we did then.
The result of sampling this way is that
one tenth of the queries are selected for
the sample.
If selected then the query
appears in the sample,
exactly as many times as it
does in the stream as a whole.
Thus the fraction of unique
queries in the sample,
should be exactly as it is for the whole.
Suppose now that we want our sample to be
not a fixed fraction of the total stream,
but a fixed number of
samples from the stream.
What we can do is hash to
a large number of buckets and
except for the example,
not just one bucket, but
enough buckets that the resulting sample
just stays within the size limit.
If, as more stream elements come
in our sample gets to large,
we pick one of the buckets we have
been including in the sample.
We delete the samp from the samples.
Just those elements that
adds to that bucket.
Organizing the sample itself by bucket
can make this decision process efficient.
I won't go into the details.
So let's rethink the example
we've been working with.
We still want to want a 10%
sample of the search-queries.
But we realize eventually.
Even the 10% percent
sample will get too large.
So we want the ability to, to throw out of
the sample some fraction of its members.
And of course we want to do it
consistently so at one occurrence of
the query is tossed, then all occurrences
of the same query are tossed.
Hashing to 10 buckets is fine,
to get a 10% sample.
We need to be prepared to deal
with smaller fractions, so
we need to hash to many more buckets.
We'll pick a 100 buckets for
our example but it could be
a million buckets or even more.
As long as we're happy with a 10%
sample then we'll accept for
the sample those elements that
hashed to 10% of the buckets.
We can choose any ten, but
let's choose 0 through 9 to be specific.
Now, suppose were going along and at some
point, the sample size gets too big.
So we pick one of the buckets
to get rid of, say bucket 9.
That is, we delete from the sample
all those elements that hashed to 9,
while retaining those that
hashed to 0 through 8.
Implementation is simple
if we store the sample by
bucket we just return bucket
9 to available space.
Now our sample is 9% of the stream.
In the future we only add to the sample
new stream elements that hash to 0
through 8.
Now, sooner or later, even the 9%
sample will exceed our space bound.
So we get rid of those elements that
hash to 8, and then 7, and so on.
If we eventually, if eventually even
a 1% sample is too much, we're stuck.
But then, we should have taken
the opportunity to hash to more buckets
than 100.
Probably lots more.
The idea we explained by example,
is really an instance of a general idea.
We can see any form of
data as key value pairs.
Hm, okay, we can choose our sample
by picking a random key set of
the desired size and
taking all key value pairs.
This key falls into the accepted set
regardless of the associated value.
In our example search queries,
the search query itself is a key and
the value was null,
it was not really there.
In general we select our
sample by hashing keys only.
The value is not part of
the argument of the hash function.
We pick an appropriate number
of buckets for acceptance, and
we add to our sample each
key-value pair whose key hashes to
one side of the exce to one
of the accepting buckets.
So let's look at a simple example,
where picking the right key
makes all the difference.
Okay, imagine that data elements
are tupled with three components.
An ID for some employee, the department
that the employee works for, and
the salary of that employee.
For each department there is a salary
range, the difference between
the maximum and minimum salaries, taken
over all the employees of that department.
Again, let's suppose we want to use
a 10% sample of those two polls,
to estimate to estimate
the average salary range.
Picking 10% of the two
polls at random won't work.
For a given department,
we're likely to be missing on or
both of the employees with the minimum or
maximum salary in that department.
Thus, the differences between the max and
min salaries in the sample for
a department, is likely to be too low.
That is,
we've introduced a bias toward the low
side by our poor sampling strategy.
The right way to sample,
is to treat only the department
component of tuples as the key.
And the other two components, the employee
ID and salary as each part of the value
in general both the key and value
parts can consist of many components.
If we sample this way, what we're doing
is sampling a subset of the departments.
But for each department of the sample,
we get all it's employees salary data and
we can get the true salary range for
that department.
When we compute the average of the ranges,
we might be off a little,
because we're sampling the ranges for
some departments rather than averaging
the ranges for all departments.
But that error, is just random noise
introduced by the sampling process.
Not a bias in one direction or
ano, another.