1
00:00:00,600 --> 00:00:04,530
If the dataless stream is arriving
too rapidly, we may not want to or

2
00:00:04,530 --> 00:00:07,040
need to look at every stream element.

3
00:00:07,040 --> 00:00:10,510
Perhaps we can get by with just a small
sample of the values in he stream.

4
00:00:12,140 --> 00:00:14,030
But we have to worry about two things.

5
00:00:14,030 --> 00:00:17,390
First, the sample better be unbiased.

6
00:00:17,390 --> 00:00:20,980
The second, the sampling process must
deserve the answer to the query, or

7
00:00:20,980 --> 00:00:22,870
queries we want to ask about the data.

8
00:00:25,435 --> 00:00:28,320
Unbaised sampling is not hard but cala,

9
00:00:28,320 --> 00:00:33,020
carelessly choosing how we sample
can distort the result of queries.

10
00:00:33,020 --> 00:00:35,710
So, after a discussion of the pitfalls,

11
00:00:35,710 --> 00:00:39,500
we'll see a method that preserves
the answer to a given query.

12
00:00:39,500 --> 00:00:42,960
Introducing only the noise that comes from
the fact that we are sampling at random.

13
00:00:46,820 --> 00:00:47,880
Let's take up an example.

14
00:00:49,370 --> 00:00:52,500
Google has a stream of search
queries coming in at all times.

15
00:00:54,770 --> 00:00:58,460
We might want to know, what fraction of
search queries received over a period,

16
00:00:58,460 --> 00:01:00,700
such as a month, are unique?

17
00:01:00,700 --> 00:01:04,238
That is, there's only one occurrence of
that search query in the entire month.

18
00:01:08,314 --> 00:01:12,070
Many questions about the stream can
be answered by sampling the stream.

19
00:01:12,070 --> 00:01:15,770
Suppose to be concrete that we randomly
select 1/10th of the queries to

20
00:01:15,770 --> 00:01:17,110
be examined.

21
00:01:17,110 --> 00:01:18,540
For example if we wanted to know,

22
00:01:18,540 --> 00:01:21,780
what fraction of the search
queries were single word queries?

23
00:01:21,780 --> 00:01:23,400
We could compute that fraction for the,

24
00:01:23,400 --> 00:01:26,529
for the sample and
be pretty sure that it was very close.

25
00:01:28,580 --> 00:01:30,360
To the fraction for the stream as a whole.

26
00:01:31,670 --> 00:01:36,640
That is, over a month, a 1/10th sample
would be a billion queries or more.

27
00:01:36,640 --> 00:01:39,890
Statistically, if those queries
are selected at random,

28
00:01:39,890 --> 00:01:42,310
the deviation from the true
answer will be miniscule.

29
00:01:46,890 --> 00:01:49,190
However, we want the fraction
of unique queries.

30
00:01:49,190 --> 00:01:51,210
And this query cannot
be answered correctly,

31
00:01:51,210 --> 00:01:52,880
from a random sample of the stream.

32
00:01:54,160 --> 00:01:57,450
In fact, as we will see on the next slide,
there's not enough information to

33
00:01:57,450 --> 00:02:01,889
deduce the fraction, for the entire
stream from the fraction with the sample.

34
00:02:03,250 --> 00:02:06,250
Let's do the math of
the matter of unique queries.

35
00:02:06,250 --> 00:02:09,513
First, we know that there will be
in the sample very close to 10%,

36
00:02:09,513 --> 00:02:11,896
of the query occurrences
of the original stream.

37
00:02:13,173 --> 00:02:17,097
The problem is that the probability of
a given query appearing to be unique in

38
00:02:17,097 --> 00:02:19,810
the sample,
gets distorted because of the sample.

39
00:02:21,750 --> 00:02:24,470
First, suppose the query is
unique in the stream as a whole.

40
00:02:24,470 --> 00:02:27,890
It has a one tenth chance of
being selected for the sample.

41
00:02:27,890 --> 00:02:28,850
That's fine.

42
00:02:28,850 --> 00:02:32,190
It says that the fraction of
truly unique queries that make it

43
00:02:32,190 --> 00:02:34,580
into the sample is the same as for
the whole stream.

44
00:02:35,690 --> 00:02:39,010
If we could only count the truly
unique queries in the sample,

45
00:02:39,010 --> 00:02:40,220
we would get the right answer.

46
00:02:42,500 --> 00:02:47,030
However, suppose a search query appears
exactly twice in the whole stream?

47
00:02:47,030 --> 00:02:51,020
The chance that the first occurrence
will be selected for the sample is 10%,

48
00:02:51,020 --> 00:02:55,860
and the chance that the second
occurrence will not be selected is 90%.

49
00:02:55,860 --> 00:02:57,120
Multiply those and

50
00:02:57,120 --> 00:03:00,620
we have a 9% chance with this query
occurrence being unique in the sample.

51
00:03:01,660 --> 00:03:06,330
Moreover the first occurrence could not be
selected, but the second is selected, and

52
00:03:06,330 --> 00:03:10,330
that's another 9% chance of
a query that really occurs twice

53
00:03:10,330 --> 00:03:12,020
looking unique in the sample.

54
00:03:12,020 --> 00:03:12,940
That's a total of 18%.

55
00:03:12,940 --> 00:03:18,970
I'll let you do the calculation,
but a query that

56
00:03:18,970 --> 00:03:24,970
appears in the stream 3 times has a 24.3%
chance of looking unique in the sample.

57
00:03:24,970 --> 00:03:29,160
And in fact, any query, no matter how many
times it appears in the original stream,

58
00:03:29,160 --> 00:03:31,800
has at least a small chance of
looking unique in the sample.

59
00:03:32,930 --> 00:03:35,480
So when we count the number of
unique queries in the sample,

60
00:03:35,480 --> 00:03:38,960
it will be an overestimate of
the true fraction of unique queries,

61
00:03:38,960 --> 00:03:41,880
very possibly a substantial overestimate.

62
00:03:41,880 --> 00:03:44,480
In fact, there could be no
unique queries in the original.

63
00:03:44,480 --> 00:03:46,610
And yet, many in the sample.

64
00:03:46,610 --> 00:03:49,190
And worse, we just don't know
from the sample whether,

65
00:03:49,190 --> 00:03:52,060
we're looking at truly unique queries,
or not.

66
00:03:52,060 --> 00:03:54,590
We may as well toss out the data,
and start over again.

67
00:03:56,560 --> 00:03:59,270
If you think about it,
the problem was that we assumed we

68
00:03:59,270 --> 00:04:02,880
flipped a ten sided coin every time
a new element arrived on the stream.

69
00:04:03,880 --> 00:04:08,280
The consequence is that when a query
occurs at several positions in the stream,

70
00:04:08,280 --> 00:04:12,500
we decided independently whether or
not to add each one to the sample.

71
00:04:12,500 --> 00:04:14,240
That isn't what we want.

72
00:04:14,240 --> 00:04:17,000
We want to pick one tenth
of the search queries,

73
00:04:17,000 --> 00:04:21,340
not one tenth of the instances of
search queries in the stream, and

74
00:04:21,340 --> 00:04:24,850
we can make the random decision
the first time we see each search query.

75
00:04:25,890 --> 00:04:29,540
If kept the table of our decision for
each search query we've ever seen,

76
00:04:29,540 --> 00:04:33,540
then each time the query appears,
we could look it up in the table.

77
00:04:33,540 --> 00:04:38,620
If we fa, if found the, the, we do the
same we did with the first occurrence of

78
00:04:38,620 --> 00:04:42,040
that query add it to the sample or not.

79
00:04:42,040 --> 00:04:46,710
But, if we didn't find the query in
the table we'd flip that ten sided coin to

80
00:04:46,710 --> 00:04:48,640
decide what to do with it.

81
00:04:48,640 --> 00:04:51,310
And we called the query and
the outcome in the table.

82
00:04:53,400 --> 00:04:55,210
That's kind of unappetizing.

83
00:04:55,210 --> 00:04:57,350
It will be hard to manage the table, and

84
00:04:57,350 --> 00:04:59,150
there is a lookup with
each stream element.

85
00:05:00,500 --> 00:05:03,220
Fortunately, there's a much simpler
way to get the same effect,

86
00:05:03,220 --> 00:05:04,220
without storing anything.

87
00:05:07,340 --> 00:05:11,363
Okay, let's pick a hash function from
search queries to 10 buckets, 0 through 9.

88
00:05:12,560 --> 00:05:14,700
When the search query arrives hash it.

89
00:05:14,700 --> 00:05:17,740
If it goes to bucket 0
then add it to the sample.

90
00:05:17,740 --> 00:05:21,295
And if it goes to any of the 9 other
buckets, do not add it to the sample.

91
00:05:24,836 --> 00:05:28,051
The cool thing about this approach
is that, all occurrences of the same

92
00:05:28,051 --> 00:05:32,480
query hash to the same bucket, because
the same hash function is always applied.

93
00:05:32,480 --> 00:05:35,880
As a result, we don't need to know whether
the search query that just arrived

94
00:05:35,880 --> 00:05:37,790
has been seen before.

95
00:05:37,790 --> 00:05:40,040
And we don't need to
know what action we took.

96
00:05:40,040 --> 00:05:42,000
We can be sure that if
it did appear before,

97
00:05:42,000 --> 00:05:44,180
we'll do the same thing
now that we did then.

98
00:05:45,380 --> 00:05:49,100
The result of sampling this way is that
one tenth of the queries are selected for

99
00:05:49,100 --> 00:05:50,350
the sample.

100
00:05:50,350 --> 00:05:52,640
If selected then the query
appears in the sample,

101
00:05:52,640 --> 00:05:56,140
exactly as many times as it
does in the stream as a whole.

102
00:05:56,140 --> 00:05:58,900
Thus the fraction of unique
queries in the sample,

103
00:05:58,900 --> 00:06:01,250
should be exactly as it is for the whole.

104
00:06:05,850 --> 00:06:09,620
Suppose now that we want our sample to be
not a fixed fraction of the total stream,

105
00:06:09,620 --> 00:06:11,710
but a fixed number of
samples from the stream.

106
00:06:15,190 --> 00:06:17,770
What we can do is hash to
a large number of buckets and

107
00:06:17,770 --> 00:06:20,340
except for the example,
not just one bucket, but

108
00:06:20,340 --> 00:06:24,430
enough buckets that the resulting sample
just stays within the size limit.

109
00:06:25,640 --> 00:06:29,200
If, as more stream elements come
in our sample gets to large,

110
00:06:29,200 --> 00:06:32,630
we pick one of the buckets we have
been including in the sample.

111
00:06:32,630 --> 00:06:34,240
We delete the samp from the samples.

112
00:06:34,240 --> 00:06:37,210
Just those elements that
adds to that bucket.

113
00:06:37,210 --> 00:06:42,080
Organizing the sample itself by bucket
can make this decision process efficient.

114
00:06:42,080 --> 00:06:43,600
I won't go into the details.

115
00:06:47,190 --> 00:06:49,710
So let's rethink the example
we've been working with.

116
00:06:49,710 --> 00:06:54,020
We still want to want a 10%
sample of the search-queries.

117
00:06:54,020 --> 00:06:55,618
But we realize eventually.

118
00:06:55,618 --> 00:06:58,900
Even the 10% percent
sample will get too large.

119
00:06:58,900 --> 00:07:02,660
So we want the ability to, to throw out of
the sample some fraction of its members.

120
00:07:02,660 --> 00:07:06,320
And of course we want to do it
consistently so at one occurrence of

121
00:07:06,320 --> 00:07:10,570
the query is tossed, then all occurrences
of the same query are tossed.

122
00:07:12,510 --> 00:07:15,300
Hashing to 10 buckets is fine,
to get a 10% sample.

123
00:07:16,440 --> 00:07:19,540
We need to be prepared to deal
with smaller fractions, so

124
00:07:19,540 --> 00:07:22,130
we need to hash to many more buckets.

125
00:07:22,130 --> 00:07:23,890
We'll pick a 100 buckets for

126
00:07:23,890 --> 00:07:27,620
our example but it could be
a million buckets or even more.

127
00:07:27,620 --> 00:07:31,760
As long as we're happy with a 10%
sample then we'll accept for

128
00:07:31,760 --> 00:07:35,860
the sample those elements that
hashed to 10% of the buckets.

129
00:07:35,860 --> 00:07:39,300
We can choose any ten, but
let's choose 0 through 9 to be specific.

130
00:07:40,970 --> 00:07:45,620
Now, suppose were going along and at some
point, the sample size gets too big.

131
00:07:45,620 --> 00:07:47,935
So we pick one of the buckets
to get rid of, say bucket 9.

132
00:07:50,790 --> 00:07:54,890
That is, we delete from the sample
all those elements that hashed to 9,

133
00:07:54,890 --> 00:07:58,480
while retaining those that
hashed to 0 through 8.

134
00:07:58,480 --> 00:08:01,480
Implementation is simple
if we store the sample by

135
00:08:01,480 --> 00:08:06,430
bucket we just return bucket
9 to available space.

136
00:08:06,430 --> 00:08:08,490
Now our sample is 9% of the stream.

137
00:08:09,560 --> 00:08:13,444
In the future we only add to the sample
new stream elements that hash to 0

138
00:08:13,444 --> 00:08:14,171
through 8.

139
00:08:16,534 --> 00:08:21,530
Now, sooner or later, even the 9%
sample will exceed our space bound.

140
00:08:21,530 --> 00:08:25,900
So we get rid of those elements that
hash to 8, and then 7, and so on.

141
00:08:25,900 --> 00:08:30,590
If we eventually, if eventually even
a 1% sample is too much, we're stuck.

142
00:08:30,590 --> 00:08:33,780
But then, we should have taken
the opportunity to hash to more buckets

143
00:08:33,780 --> 00:08:35,078
than 100.

144
00:08:35,078 --> 00:08:36,153
Probably lots more.

145
00:08:40,535 --> 00:08:44,764
The idea we explained by example,
is really an instance of a general idea.

146
00:08:44,764 --> 00:08:47,536
We can see any form of
data as key value pairs.

147
00:08:51,246 --> 00:08:55,105
Hm, okay, we can choose our sample
by picking a random key set of

148
00:08:55,105 --> 00:08:58,480
the desired size and
taking all key value pairs.

149
00:08:58,480 --> 00:09:02,386
This key falls into the accepted set
regardless of the associated value.

150
00:09:06,390 --> 00:09:09,821
In our example search queries,
the search query itself is a key and

151
00:09:09,821 --> 00:09:12,160
the value was null,
it was not really there.

152
00:09:14,970 --> 00:09:18,680
In general we select our
sample by hashing keys only.

153
00:09:18,680 --> 00:09:21,390
The value is not part of
the argument of the hash function.

154
00:09:23,610 --> 00:09:26,240
We pick an appropriate number
of buckets for acceptance, and

155
00:09:26,240 --> 00:09:30,860
we add to our sample each
key-value pair whose key hashes to

156
00:09:30,860 --> 00:09:33,840
one side of the exce to one
of the accepting buckets.

157
00:09:38,560 --> 00:09:40,060
So let's look at a simple example,

158
00:09:40,060 --> 00:09:42,159
where picking the right key
makes all the difference.

159
00:09:45,300 --> 00:09:48,720
Okay, imagine that data elements
are tupled with three components.

160
00:09:48,720 --> 00:09:53,200
An ID for some employee, the department
that the employee works for, and

161
00:09:53,200 --> 00:09:54,540
the salary of that employee.

162
00:09:56,080 --> 00:09:59,090
For each department there is a salary
range, the difference between

163
00:09:59,090 --> 00:10:03,259
the maximum and minimum salaries, taken
over all the employees of that department.

164
00:10:05,370 --> 00:10:09,500
Again, let's suppose we want to use
a 10% sample of those two polls,

165
00:10:09,500 --> 00:10:11,630
to estimate to estimate
the average salary range.

166
00:10:13,842 --> 00:10:16,470
Picking 10% of the two
polls at random won't work.

167
00:10:17,750 --> 00:10:20,330
For a given department,
we're likely to be missing on or

168
00:10:20,330 --> 00:10:25,090
both of the employees with the minimum or
maximum salary in that department.

169
00:10:25,090 --> 00:10:27,310
Thus, the differences between the max and

170
00:10:27,310 --> 00:10:31,600
min salaries in the sample for
a department, is likely to be too low.

171
00:10:31,600 --> 00:10:32,117
That is,

172
00:10:32,117 --> 00:10:36,279
we've introduced a bias toward the low
side by our poor sampling strategy.

173
00:10:40,115 --> 00:10:41,258
The right way to sample,

174
00:10:41,258 --> 00:10:44,840
is to treat only the department
component of tuples as the key.

175
00:10:44,840 --> 00:10:48,910
And the other two components, the employee
ID and salary as each part of the value

176
00:10:50,220 --> 00:10:53,910
in general both the key and value
parts can consist of many components.

177
00:10:55,110 --> 00:11:00,460
If we sample this way, what we're doing
is sampling a subset of the departments.

178
00:11:00,460 --> 00:11:05,310
But for each department of the sample,
we get all it's employees salary data and

179
00:11:05,310 --> 00:11:07,910
we can get the true salary range for
that department.

180
00:11:09,260 --> 00:11:12,890
When we compute the average of the ranges,
we might be off a little,

181
00:11:12,890 --> 00:11:14,980
because we're sampling the ranges for

182
00:11:14,980 --> 00:11:19,290
some departments rather than averaging
the ranges for all departments.

183
00:11:19,290 --> 00:11:23,530
But that error, is just random noise
introduced by the sampling process.

184
00:11:23,530 --> 00:11:27,399
Not a bias in one direction or
ano, another.