1
00:00:00,650 --> 00:00:01,250
We're now going to

2
00:00:01,250 --> 00:00:05,270
take up a particular problem that
has a very non-trivial solution.

3
00:00:05,270 --> 00:00:08,536
We assume the stream elements are bits,
zeroes or

4
00:00:08,536 --> 00:00:12,360
one, and we want to know how
many bits in the last N are one.

5
00:00:13,760 --> 00:00:15,590
If we can store the most recent N bits,

6
00:00:15,590 --> 00:00:18,360
we can use the solution like
the one discussed for averages.

7
00:00:18,360 --> 00:00:20,240
In fact the algorithm
would be even simpler.

8
00:00:21,520 --> 00:00:24,850
However, we're going to address
the situation where N bits don't fit

9
00:00:24,850 --> 00:00:25,680
in main memory.

10
00:00:25,680 --> 00:00:30,080
Perhaps N is a trillion or
N is a reasonable number but

11
00:00:30,080 --> 00:00:34,110
there, there are so many streams that we
can't store complete windows for all.

12
00:00:35,380 --> 00:00:39,160
If we want exact answers then we can
show that it is impossible to do

13
00:00:39,160 --> 00:00:42,070
anything better than to
store the entire window.

14
00:00:42,070 --> 00:00:46,484
However, what is interesting is
that we can store on the order of

15
00:00:46,484 --> 00:00:50,405
the square of log in bits,
where N is the window size, and

16
00:00:50,405 --> 00:00:55,475
still answer queries about the counted
ones with answers that are off by at

17
00:00:55,475 --> 00:00:59,688
most a small factor,
as small as we like if we do enough work.

18
00:01:04,219 --> 00:01:06,970
The problem we're going
to discuss is this.

19
00:01:06,970 --> 00:01:08,160
We're given a stream of 0's and 1's.

20
00:01:08,160 --> 00:01:12,650
At any time we have to be prepared
to answer a query of the form.

21
00:01:12,650 --> 00:01:15,295
How many of the last k bits were one?

22
00:01:15,295 --> 00:01:19,703
Here k can be any integer from one
up to some large upper limit N.

23
00:01:23,942 --> 00:01:29,720
We can surely do this if we use a windows
size N and store the last N bits.

24
00:01:29,720 --> 00:01:33,393
When a new bit arrives, we throw away
the oldest bit in the windows since it

25
00:01:33,393 --> 00:01:36,250
can never again be useful to
answer one of these queries.

26
00:01:38,633 --> 00:01:43,224
But one disadvantage of this approach is
that answering one query requires that we

27
00:01:43,224 --> 00:01:46,748
examine k bits, since k can be
quite large, and both inputs and

28
00:01:46,748 --> 00:01:50,898
queries may be arriving very rapidly,
that may be time we cannot afford.

29
00:01:53,406 --> 00:01:56,900
Another potential problem is that we
may not be able to afford the space.

30
00:01:56,900 --> 00:02:03,200
As we just mentioned we could be trying
to handle a large number of streams or

31
00:02:03,200 --> 00:02:06,690
N could be so large that even one
window does not fit in main memory.

32
00:02:08,620 --> 00:02:12,978
Both these concerns suggests that we
should consider a method that uses less

33
00:02:12,978 --> 00:02:13,806
than N space.

34
00:02:13,806 --> 00:02:17,272
And that also allows us to
answer queries about the last k

35
00:02:17,272 --> 00:02:20,008
bits much faster than on the order of k.

36
00:02:20,008 --> 00:02:24,313
It turns out that we can't get an exact
answer to queries without using N

37
00:02:24,313 --> 00:02:25,552
bits in the window.

38
00:02:25,552 --> 00:02:28,831
But we can get close using
much less space than all of N,

39
00:02:28,831 --> 00:02:31,056
and also much less time than all of k.

40
00:02:34,675 --> 00:02:37,619
We're going to introduce the right
algorithm with the discussion of

41
00:02:37,619 --> 00:02:41,010
something that seems like it
should work but doesn't quite.

42
00:02:41,010 --> 00:02:43,640
Our goal was the be off by no
more than a factor of 2 in

43
00:02:43,640 --> 00:02:47,040
estimating the number of
ones in the last k bits.

44
00:02:47,040 --> 00:02:52,080
So we will summarize blocks of the stream
as blocks will have exponentially

45
00:02:52,080 --> 00:02:58,250
increasing lengths, that is 1,
2, 4, 8, 16, so on.

46
00:03:02,590 --> 00:03:05,520
And the summary of a block
will be simply the count of

47
00:03:05,520 --> 00:03:06,780
the number of ones in that block.

48
00:03:06,780 --> 00:03:11,850
When we want to know the count of ones for
last k bits, we can find

49
00:03:11,850 --> 00:03:16,800
some blocks that lie wholly within the
last k bits and we add up their counts.

50
00:03:16,800 --> 00:03:20,760
It is only the last block, the one
furthest back in time that gives us pause.

51
00:03:20,760 --> 00:03:25,020
We don't know how many of its ones within
the last k bits so we have to guess.

52
00:03:29,873 --> 00:03:33,225
But if we've created these
exponentially growing blocks for

53
00:03:33,225 --> 00:03:37,543
all time units then there would be as many
blocks of length one as there are bits in

54
00:03:37,543 --> 00:03:42,050
the window, as well as blocks or
size two, four, eight, and so on.

55
00:03:42,050 --> 00:03:44,140
So that saves us nothing.

56
00:03:44,140 --> 00:03:47,600
Instead, we have to drop blocks if their
left end, that is, the end that is

57
00:03:47,600 --> 00:03:52,240
earliest in time, coincides with
the left end of the larger block.

58
00:03:52,240 --> 00:03:57,130
And we also drop a small block if there's
a larger block completely to their right,

59
00:03:57,130 --> 00:03:58,560
that is, later in the stream.

60
00:03:59,810 --> 00:04:03,340
As a result, you never have more
than two blocks of any one size.

61
00:04:06,700 --> 00:04:11,150
So, here is an example of the blocks
we might retain at some time.

62
00:04:11,150 --> 00:04:18,770
The five rows of blocks are of lengths 1,
2, 4, 8 and 16.

63
00:04:23,223 --> 00:04:25,564
Okay, there are two blocks of length 1.

64
00:04:28,460 --> 00:04:33,201
The more recent has a count of 0
because it consists of a single 0.

65
00:04:33,201 --> 00:04:36,074
That's this.

66
00:04:36,074 --> 00:04:43,234
While the other has a count of 1
because it consists of a single 1.

67
00:04:43,234 --> 00:04:44,160
'Kay?

68
00:04:44,160 --> 00:04:46,654
Here's a block of length 2.

69
00:04:48,380 --> 00:04:53,450
That has a count of 1
because it represents 0 1.

70
00:04:53,450 --> 00:04:54,440
That is, these two bits.

71
00:04:55,600 --> 00:04:59,640
Notice that we've previously deleted
the block of length 1 that would go here,

72
00:05:01,820 --> 00:05:08,468
because it begins at the same point
as the block of length 2 above it.

73
00:05:08,468 --> 00:05:13,442
Also all other blocks of length
1 are deleted because they have

74
00:05:13,442 --> 00:05:16,950
a block of length 2
completely to their right.

75
00:05:19,200 --> 00:05:22,490
We also show a second block of length 2.

76
00:05:22,490 --> 00:05:27,560
Its count is 2 because it represents,
this 1 1.

77
00:05:29,190 --> 00:05:37,510
There are two blocks of length 4 and
they have counts of 2 and 3.

78
00:05:37,510 --> 00:05:45,679
They represent, well, this guy represents
this sequence, 0 0 1 1, so it has two 1's.

79
00:05:45,679 --> 00:05:50,684
This represents 1 0 1 1 and

80
00:05:50,684 --> 00:05:55,696
therefore gets a count of 3.

81
00:05:55,696 --> 00:05:56,445
'Kay.

82
00:06:02,207 --> 00:06:05,342
We see one block of length 8.

83
00:06:05,342 --> 00:06:07,827
Its count is 4.

84
00:06:07,827 --> 00:06:15,850
Well let's see,
because it represents these eight bits.

85
00:06:19,160 --> 00:06:24,080
And notice that, that the count for
second block of length 8 is not

86
00:06:24,080 --> 00:06:28,650
needed because we can
figure out it has six ones.

87
00:06:28,650 --> 00:06:34,088
Since that's tad, that 6 is
the difference between the number of

88
00:06:34,088 --> 00:06:40,002
ones in this block of length 16 and
that block of length 8.

89
00:06:40,002 --> 00:06:45,217
Or that is 10 minus 4 equals 6.

90
00:06:45,217 --> 00:06:50,974
So if this block existed,
it would have, surely have six once.

91
00:06:55,012 --> 00:06:55,731
Okay.

92
00:06:55,731 --> 00:07:02,449
Now, suppose we get a query for how many
ones there are in the most recent 28 bits.

93
00:07:04,290 --> 00:07:06,370
We can add up the counts
of certain blocks.

94
00:07:06,370 --> 00:07:10,620
Some little blocks at the right end, and
then some bigger blocks going to the left.

95
00:07:10,620 --> 00:07:14,710
We want to pick blocks so that each of
the most recent 28 bits is covered by

96
00:07:14,710 --> 00:07:16,700
exactly one of the blocks we choose.

97
00:07:17,920 --> 00:07:22,975
So, we pick this block of length 1.

98
00:07:25,080 --> 00:07:27,080
This block of length 2.

99
00:07:27,080 --> 00:07:29,150
This of length 4.

100
00:07:29,150 --> 00:07:34,410
We don't want this block of length 8
because we have this block of length

101
00:07:34,410 --> 00:07:41,544
16 and
that's still all within the last 28.

102
00:07:41,544 --> 00:07:47,771
so, so far we have covered 23 bits and

103
00:07:47,771 --> 00:07:53,433
we know that among them the number of

104
00:07:53,433 --> 00:07:59,282
1's is 0 plus 1 plus 2 plus 10,

105
00:07:59,282 --> 00:08:06,750
which is 13 Okay but
what do we do about the oldest five bits?

106
00:08:08,038 --> 00:08:13,444
We that is, there are these bits now,
if we could see the bits we would know

107
00:08:13,444 --> 00:08:19,400
that they're 0 0 1 0 1 therefor they
have two 1's, but we don't see them.

108
00:08:19,400 --> 00:08:24,120
All we see is that they are part
of this block of 16 and

109
00:08:24,120 --> 00:08:29,590
we know that block has a count of six,

110
00:08:30,660 --> 00:08:35,700
okay, but we can't tell how many of those
six are in the most recent five positions.

111
00:08:35,700 --> 00:08:39,700
Again, we don't ever get
to see this anymore.

112
00:08:39,700 --> 00:08:43,050
Now if we could see them of course
we would know there were two and

113
00:08:43,050 --> 00:08:44,379
that the right answer is 15.

114
00:08:46,790 --> 00:08:53,150
But we need to estimate, without seeing
how many ones there are in this region.

115
00:08:55,032 --> 00:09:01,313
Okay if we guess that half
the count of the block that is 3,

116
00:09:01,313 --> 00:09:06,696
6 divided by 2 in this
case is is in the region

117
00:09:06,696 --> 00:09:12,080
we don't see then we would guess 16 and

118
00:09:12,080 --> 00:09:17,371
that's only off by 7% so
that's not even bad.

119
00:09:17,371 --> 00:09:22,320
We could even try a proportional
guess that is say,

120
00:09:22,320 --> 00:09:28,072
we know that there is 6 with,
in 6 divided by 16, well,

121
00:09:28,072 --> 00:09:33,366
6 divided by 16 is the probability
that any given bit

122
00:09:33,366 --> 00:09:39,350
is 1 in the range represented by this,
by this block of 16,

123
00:09:39,350 --> 00:09:43,951
and we know that we have
to count five of them, so

124
00:09:43,951 --> 00:09:49,015
that's 30 divided by 16,
which is roughly 2,

125
00:09:49,015 --> 00:09:54,583
and so if we guess 2, and
added that, we would get 15.

126
00:09:54,583 --> 00:10:00,199
And that happens to be right on the mark
even though we didn't get to see the,

127
00:10:00,199 --> 00:10:03,480
the, the five bits that
we wanted to count those.

128
00:10:05,150 --> 00:10:06,986
This strategy has a lot to recommend it.

129
00:10:08,150 --> 00:10:15,450
Okay, first it stores only
the square of log N bits.

130
00:10:15,450 --> 00:10:22,520
I might comment that we use log,
we use this expression (log2N)

131
00:10:22,520 --> 00:10:27,720
to mean the square of log N.

132
00:10:27,720 --> 00:10:29,480
Okay this is a, a, a common expression.

133
00:10:29,480 --> 00:10:34,690
You don't want to write it as log N
squared because that's really 2 2 log N,

134
00:10:34,690 --> 00:10:36,830
which is not what we mean.

135
00:10:40,210 --> 00:10:43,980
So I, I should, if you've never seen
this notation before again the putting

136
00:10:43,980 --> 00:10:49,680
the square above the log means that
you're actually squaring the whole thing.

137
00:10:49,680 --> 00:10:51,150
The, the squaring log N.

138
00:10:52,560 --> 00:10:57,459
okay, now.

139
00:10:58,870 --> 00:11:02,990
As I said, okay square, storing square
of log N bits is not that bad, okay?

140
00:11:04,276 --> 00:11:08,969
It's much less than N for,
for for large N.

141
00:11:08,969 --> 00:11:14,169
So if N is a billion,
then log squared N is about 900.

142
00:11:14,169 --> 00:11:19,390
Now why do we need only on
the order of log squared N bits?

143
00:11:19,390 --> 00:11:20,070
Well first of all,

144
00:11:20,070 --> 00:11:24,540
if the window size is N bits, we never
need any blocks of length greater than N.

145
00:11:24,540 --> 00:11:28,510
An account up to n can be stored
in log based 2 of N bits.

146
00:11:30,700 --> 00:11:32,080
Now how many counts do we need?

147
00:11:33,330 --> 00:11:41,060
Well, there are only log based 2 N box
sizes from 1 1 to 4, 8, 16 and so on.

148
00:11:42,670 --> 00:11:46,590
Up to the largest power of 2 that
are long, are no larger than N.

149
00:11:46,590 --> 00:11:51,529
So we never store more than
two blocks of any size.

150
00:11:51,529 --> 00:11:54,240
And as a result, we need to store at most,

151
00:11:54,240 --> 00:11:59,052
2 log N counts, of at most log in bits
each, and that's 2 log squared N.

152
00:12:06,812 --> 00:12:10,620
Another good thing is that after each
bit we do a limited amount of work.

153
00:12:10,620 --> 00:12:12,820
We have to create a new
block of length 1 for

154
00:12:12,820 --> 00:12:15,260
each of the lengths 1, 2, 4, 8, and so on.

155
00:12:15,260 --> 00:12:19,830
We may have to drop a block of that length
or we may have to combine two blocks of

156
00:12:19,830 --> 00:12:23,520
one length into two blocks
of the next larger length.

157
00:12:23,520 --> 00:12:27,592
But that means that most order log N
were total since there were log N sizes.

158
00:12:32,476 --> 00:12:34,780
And the error is frequently small.

159
00:12:34,780 --> 00:12:37,270
It can't be bigger than
the count of the biggest block.

160
00:12:37,270 --> 00:12:39,987
The one that is only partially
in the region we're counting.

161
00:12:41,610 --> 00:12:43,730
There's a problem with the scheme,
however.

162
00:12:43,730 --> 00:12:47,494
When the 1's are distributed evenly
among all the regions of the stream,

163
00:12:47,494 --> 00:12:50,123
the number of 1's in
the ambiguous region can't be

164
00:12:50,123 --> 00:12:53,663
more than half the total number of
1's in the region we want to count.

165
00:12:53,663 --> 00:12:58,120
So our error is limited to 50%, but
look what happens if all the ones in

166
00:12:58,120 --> 00:13:02,212
the region we want to count are at
the left end, and in particular,

167
00:13:02,212 --> 00:13:06,700
are counted only by a block that is
partially within the desired region.

168
00:13:07,960 --> 00:13:11,800
Then the true count could be anything from
0 up to the full count of that block.

169
00:13:12,950 --> 00:13:15,670
Anything we guess could be wildly wrong,
and we'll never know.

170
00:13:19,680 --> 00:13:23,340
We're therefore going to discuss a similar
algorithm that preserves the good and

171
00:13:23,340 --> 00:13:25,560
avoids the problem with
uneven distribution of 1's.

172
00:13:25,560 --> 00:13:31,070
We'll still divide the window into blocks,
but instead of letting each block cover

173
00:13:31,070 --> 00:13:35,580
a fixed segment of the string, we'll let
each block cover a fixed number of 1's.

174
00:13:36,770 --> 00:13:40,820
The sizes of the blocks will still
be limited to the powers of 2.

175
00:13:40,820 --> 00:13:46,860
That is 1, 2, 4, 8, and so on, but
the notion of the size of a block changes.

176
00:13:46,860 --> 00:13:49,750
Now the size of a block
will be the number of 1's.

177
00:13:49,750 --> 00:13:52,910
So we'll have blocks of size
1 to represent segments in

178
00:13:52,910 --> 00:13:54,980
the stream that have a single 1.

179
00:13:54,980 --> 00:13:59,550
Blocks with twice that size will
represent two 1's and number of 0's.

180
00:13:59,550 --> 00:14:04,806
And then there will be blocks representing
four 1's and any number of 0's and so on.

181
00:14:04,806 --> 00:14:09,680
The advantage of this scheme is that
there are few 1's in the resent stream,

182
00:14:09,680 --> 00:14:13,320
the block size covering that
region will stay small.

183
00:14:13,320 --> 00:14:18,597
They will cover large parts of the stream,
while their size, or

184
00:14:18,597 --> 00:14:21,439
number of 1's remains limited.

185
00:14:21,439 --> 00:14:26,965
I decided to call the algorithm I'm
going to describe the DGIM algorithm.

186
00:14:26,965 --> 00:14:32,647
The initials refers to the four guys who
invented this algorithm Mayur Datar,

187
00:14:32,647 --> 00:14:37,470
Aristides Gionis, Piotr Indyk,
and Rajeev Motwani.

188
00:14:37,470 --> 00:14:39,240
And in fact,
this is a good time to stop and

189
00:14:39,240 --> 00:14:44,410
remember Rajeev Motwani who died shortly
after this algorithm was published.

190
00:14:44,410 --> 00:14:48,060
He along with Gionis and
Indyk is also responsible for

191
00:14:48,060 --> 00:14:51,579
locality sensitive hashing which
forms a major part of this course.

192
00:14:54,110 --> 00:14:57,443
Like our earlier attempt and an algorithm,

193
00:14:57,443 --> 00:15:03,216
a DGIM stores on the order of (log2N)bits,
to represent 1N bit window.

194
00:15:03,216 --> 00:15:08,167
There's an absolute guarantee of no more
than 50% error in the answer to any query.

195
00:15:11,123 --> 00:15:16,240
And if 50% is too much, you can reduce
the error to anything greater than 0.

196
00:15:16,240 --> 00:15:20,457
The algorithm becomes more complicated
on the number of bits you need to

197
00:15:20,457 --> 00:15:25,113
store grow although the number of bits
remains proportionate to (log2N).

198
00:15:25,113 --> 00:15:28,872
It's just the constant factor that
grows in inverse proportion to

199
00:15:28,872 --> 00:15:30,355
the desired error bound.

200
00:15:35,031 --> 00:15:38,440
Okay, to begin the story we need to
introduce the idea of a timestamp.

201
00:15:38,440 --> 00:15:41,290
Every bit that arrives in
the stream gets a timestamp.

202
00:15:42,870 --> 00:15:45,560
You might think that we need
an arbitrary number of bits to

203
00:15:45,560 --> 00:15:49,770
represent the time stamp since there's
no limit on how long the stream can be.

204
00:15:49,770 --> 00:15:53,030
But it's really only necessary to
represent timestamps modulo N,

205
00:15:53,030 --> 00:16:00,080
the window size that is we can divide
the timestamp by N and take the remainder.

206
00:16:00,080 --> 00:16:04,392
The net effect is the timestamp
start out at 0, 1, and so

207
00:16:04,392 --> 00:16:08,712
on up to N minus 1 and
then go to 0 again, 1, 2 and so on.

208
00:16:08,712 --> 00:16:11,430
Regardless of where
the window is in the stream,

209
00:16:11,430 --> 00:16:14,094
its N bits will all have
different timestamps.

210
00:16:18,466 --> 00:16:22,580
We're going to partition the window
of length N into buckets.

211
00:16:22,580 --> 00:16:24,810
Each bucket is represented by a record,
and

212
00:16:24,810 --> 00:16:27,860
records can be stored in
on the order of log N bits.

213
00:16:29,070 --> 00:16:34,170
As we shall see, we only need on the order
of log N buckets to represent the window,

214
00:16:34,170 --> 00:16:37,380
so on the order of log
squared N bits suffices.

215
00:16:37,380 --> 00:16:40,870
The record contents are the following.

216
00:16:42,860 --> 00:16:44,410
The timestamp of its end.

217
00:16:44,410 --> 00:16:47,390
The most recently arrived bit.

218
00:16:47,390 --> 00:16:50,070
As I mentioned we'll record
timestamps modulo N.

219
00:16:50,070 --> 00:16:52,810
So we need log N bits to
represent the timestamp.

220
00:16:54,970 --> 00:16:59,760
The number of 1's between beginning and
the end of the segment.

221
00:16:59,760 --> 00:17:04,480
We call this count of 1's
the size of the bucket.

222
00:17:04,480 --> 00:17:08,868
However the number of 1's in this
segment represented by a bucket must be

223
00:17:08,868 --> 00:17:09,730
a power of 2.

224
00:17:09,730 --> 00:17:15,248
That explains why we only need log log
N bits to represent the count of 1's.

225
00:17:20,828 --> 00:17:24,753
We can store the logarithm of the count
instead of the count itself since,

226
00:17:24,753 --> 00:17:28,150
we know that log base to
the count must be an integer.

227
00:17:28,150 --> 00:17:30,740
The count itself can't be higher then N so

228
00:17:30,740 --> 00:17:34,390
it's logarithm can't be
higher than log base 2 of N.

229
00:17:34,390 --> 00:17:37,877
Since the logarithm is an integer r i, and

230
00:17:37,877 --> 00:17:43,524
we only need log i bits to represent
the i in binary, log log N bit suffices.

231
00:17:43,524 --> 00:17:46,763
It really doesn't matter much,
since we still need order log N

232
00:17:46,763 --> 00:17:50,566
bits in the record for the bucket,
just to store the timestamp of its end.

233
00:17:56,749 --> 00:18:02,429
The partition into buckets
must obey the following rules.

234
00:18:02,429 --> 00:18:03,437
There must be one or

235
00:18:03,437 --> 00:18:07,450
two buckets of each allowed sides
up to the maximum size we need.

236
00:18:07,450 --> 00:18:09,769
Remember that allowed size
is of the power-of-2.

237
00:18:12,560 --> 00:18:14,666
No bit of the window is
part of two buckets.

238
00:18:14,666 --> 00:18:17,260
Some 0's in the stream may
not belong to any bucket.

239
00:18:17,260 --> 00:18:19,669
It, it, it doesn't matter.

240
00:18:19,669 --> 00:18:23,974
But buckets can only increase in
size as we, as we go back in time.

241
00:18:23,974 --> 00:18:30,763
The most recent part of the window is
represented by the smallest buckets.

242
00:18:30,763 --> 00:18:34,858
When the end time stamp of a bucket is
more than end-time units in the past,

243
00:18:34,858 --> 00:18:37,393
it no longer represents
part of the window, so

244
00:18:37,393 --> 00:18:40,773
we delete it from the set of
buckets whose records are stored.

245
00:18:44,478 --> 00:18:48,447
Here is a picture of what the partition of
a stream into buckets might look like at

246
00:18:48,447 --> 00:18:50,080
some point.

247
00:18:50,080 --> 00:18:56,455
The most recent two 1's are in
bucket of size 1 by themselves,

248
00:18:56,455 --> 00:18:58,943
and it's here and here.

249
00:18:58,943 --> 00:19:05,886
Further back, the previous two 1's
are grouped into a bucket of size 2.

250
00:19:05,886 --> 00:19:09,874
It's that there might be
two buckets of size 2 but

251
00:19:09,874 --> 00:19:13,440
there could also only
be one as in this case.

252
00:19:14,865 --> 00:19:22,090
Then going further back in time we see the
previous four 1's in a bucket of size 4,

253
00:19:22,090 --> 00:19:25,235
and the four 1's before that
are also in a bucket of size 4.

254
00:19:28,620 --> 00:19:31,913
Then we see two buckets of size 8.

255
00:19:31,913 --> 00:19:34,775
And finally a bucket of size 16.

256
00:19:34,775 --> 00:19:39,796
The end-time stamp of this bucket is
still within the window of length N.

257
00:19:39,796 --> 00:19:40,720
That's this.

258
00:19:42,820 --> 00:19:44,759
Although its beginning
is outside the window.

259
00:19:46,970 --> 00:19:50,790
We still need this bucket, but any
previous buckets have a time stamp that is

260
00:19:50,790 --> 00:19:54,730
prior to the beginning of the current
window, so we have deleted their records.

261
00:19:56,160 --> 00:19:59,400
So let's see how we manage the buckets
as bits arrive on the stream.

262
00:19:59,400 --> 00:20:02,650
The first thing we're going to do

263
00:20:02,650 --> 00:20:06,050
is worry about whether we need
to drop the oldest bucket.

264
00:20:06,050 --> 00:20:08,600
We need to keep outside
the bucket representation,

265
00:20:08,600 --> 00:20:12,230
the count of the number of bits that
have ever arrived in the screen.

266
00:20:12,230 --> 00:20:16,810
However we only need this count modulo N
so an extra log in bits is all we need.

267
00:20:18,060 --> 00:20:21,250
When a new bit come in,
increment that count.

268
00:20:21,250 --> 00:20:24,430
Of course if the count reaches
N then we set it back to 0.

269
00:20:24,430 --> 00:20:27,918
That's how modular arithmetic works.

270
00:20:27,918 --> 00:20:30,197
Now, look at the end-time
of the oldest bucket.

271
00:20:32,945 --> 00:20:36,853
If its time stamp agrees with the current
time, then that time stamp is

272
00:20:36,853 --> 00:20:41,370
really the current time minus N since
we're computing all time stamps modulo N.

273
00:20:42,640 --> 00:20:47,150
The entire oldest bucket is therefore out
of the window and we delete its record.

274
00:20:47,150 --> 00:20:52,413
But if the time stamp is anything
else then the oldest bucket still has

275
00:20:52,413 --> 00:20:55,692
it's end within the window so it remains.

276
00:20:55,692 --> 00:20:59,569
What we do next depends on whether
the bit that just entered is 0 or 1.

277
00:20:59,569 --> 00:21:03,460
If it's 0, then we make no further
changes to the set of buckets.

278
00:21:03,460 --> 00:21:04,182
That was easy.

279
00:21:07,716 --> 00:21:10,330
If the current input is 1,
we have some work to do.

280
00:21:10,330 --> 00:21:15,924
But the work is at most
logarithmic in the window size N.

281
00:21:15,924 --> 00:21:19,416
First we create a new bucket for
the new bit.

282
00:21:19,416 --> 00:21:22,950
The size of the bucket is 1, and
its ending timestamp is the current time.

283
00:21:29,120 --> 00:21:32,045
There might have been one or
two buckets of size 1 previously.

284
00:21:32,045 --> 00:21:35,870
If there's only one,
now there are two, and that's fine.

285
00:21:37,320 --> 00:21:39,730
We are allowed to have one or
two of any size.

286
00:21:39,730 --> 00:21:43,810
But, if there we previously two,
now there are three.

287
00:21:43,810 --> 00:21:45,990
We can't have three buckets of size 1 so

288
00:21:45,990 --> 00:21:50,340
we combine the oldest two
into one bucket of size 2.

289
00:21:50,340 --> 00:21:54,760
Combining consecutive buckets
of the same size is easy.

290
00:21:56,130 --> 00:21:59,638
We add 1 to the logarithm of the size, and

291
00:21:59,638 --> 00:22:06,530
we take the N timestamp to be the N
timestamp of the more recent of the two.

292
00:22:06,530 --> 00:22:10,370
So, for
example here are two buckets could be of,

293
00:22:10,370 --> 00:22:14,270
of consecutive buckets of any size,
let's say 2 to the x.

294
00:22:17,040 --> 00:22:23,270
We combine them into one bucket
of size 2 to the x plus 1,

295
00:22:23,270 --> 00:22:29,980
by simply,
this bucket gets this ending time.

296
00:22:29,980 --> 00:22:31,980
I just copy it from here.

297
00:22:33,160 --> 00:22:39,660
And we add 1 to the size,
which essentially says, therefore it's,

298
00:22:39,660 --> 00:22:44,590
sorry, the size is doubled and
then we just make that go away.

299
00:22:46,100 --> 00:22:47,720
But our work might not be over.

300
00:22:47,720 --> 00:22:52,560
If we had to create a bucket of size 2
we might now have three of that size.

301
00:22:52,560 --> 00:22:56,530
So we combine the earliest two
into one bucket of size 4.

302
00:22:56,530 --> 00:22:59,620
And the problem could
ripple through the sizes.

303
00:22:59,620 --> 00:23:03,230
If we just created a third bucket of size
4 then we could have three buckets of

304
00:23:03,230 --> 00:23:04,280
size 4.

305
00:23:04,280 --> 00:23:08,340
We need to combine the earliest two
into a bucket of size 8 and so on.

306
00:23:08,340 --> 00:23:11,640
But because we're doubling the bucket's
size each time we pass the problem to

307
00:23:11,640 --> 00:23:16,360
the next level, after log N fix ups
we've reached a bucket size as large as

308
00:23:16,360 --> 00:23:19,305
the entire window and
there's never need for a larger bucket.

309
00:23:19,305 --> 00:23:20,270
'Kay.

310
00:23:20,270 --> 00:23:24,670
The rippling effect therefore
stops after at most log N rounds.

311
00:23:24,670 --> 00:23:28,072
And each round may,
takes a constant amount of work.

312
00:23:28,072 --> 00:23:31,990
So O(logN) is a guaranteed upper
bound on the total time needed

313
00:23:31,990 --> 00:23:33,950
to process an incoming 1.

314
00:23:33,950 --> 00:23:38,330
Usually the, the time required is much
less, and on the average, it is constant.

315
00:23:40,510 --> 00:23:45,002
On this slide, we'll see the changes
that occur as bits enter the system.

316
00:23:45,002 --> 00:23:47,285
So here's the initial state of the window.

317
00:23:49,733 --> 00:23:53,251
A 1 enters.

318
00:23:53,251 --> 00:23:59,629
We create a bucket of size 1 for it, this.

319
00:24:03,718 --> 00:24:05,800
But now they have three buckets of size 1.

320
00:24:07,090 --> 00:24:11,130
So we're going to have to
combine the two earliest 1's.

321
00:24:11,130 --> 00:24:12,242
This one.

322
00:24:12,242 --> 00:24:13,140
And that one.

323
00:24:16,507 --> 00:24:20,801
Okay, so here we've done the combination.

324
00:24:20,801 --> 00:24:26,972
What has happened in terms of
the records is that the record for

325
00:24:26,972 --> 00:24:30,064
this bucket is deleted.

326
00:24:30,064 --> 00:24:36,611
The size for
this record has changed from 1 to 2.

327
00:24:36,611 --> 00:24:42,050
And it's time stamp has not changed, it
has therefor actually become this record.

328
00:24:42,050 --> 00:24:43,132
And notice that,

329
00:24:43,132 --> 00:24:48,194
that 1 is really inside of the record that
this slide is not shown perfectly there.

330
00:24:48,194 --> 00:24:54,550
Now I'm showing what happens
after another 101 arrives.

331
00:24:54,550 --> 00:24:57,949
Okay?
The first of these 1's created this

332
00:24:57,949 --> 00:25:04,530
bucket, and then the 0 came in
represented that nothing changed.

333
00:25:04,530 --> 00:25:05,915
And then this next 1 arrives.

334
00:25:07,870 --> 00:25:09,800
And now, we get a third bucket of size 1.

335
00:25:09,800 --> 00:25:16,800
Okay, so that causes these two
buckets to get combined into this guy.

336
00:25:21,450 --> 00:25:25,930
And now we have three buckets of size 2.

337
00:25:25,930 --> 00:25:31,639
So, we have to combine these
two by that one really belongs

338
00:25:31,639 --> 00:25:36,778
in the in, in,
in the middle bucket of size 2.

339
00:25:36,778 --> 00:25:44,921
So, we combine these two
into to a bucket size 4.

340
00:25:44,921 --> 00:25:50,622
And that made three buckets of size 4 so
these guys got combined into

341
00:25:50,622 --> 00:25:55,860
that bucket of size 8, but
that was a third bucket of size 8.

342
00:25:55,860 --> 00:26:00,380
So these buckets of size 8 got
combined into that bucket size 16

343
00:26:01,580 --> 00:26:03,760
now there can't be more
buckets of size 16.

344
00:26:03,760 --> 00:26:08,932
There's this one but that extends
beyond the end of the of the window.

345
00:26:08,932 --> 00:26:13,341
So we're done rippling changes
to larger and larger buckets.

346
00:26:20,107 --> 00:26:22,360
Now I want to explain
how to query the system.

347
00:26:23,670 --> 00:26:27,130
So suppose we want to know how
many 1's there are in the last k

348
00:26:27,130 --> 00:26:30,450
bits where k is any integer less than or
equal to N, the window size.

349
00:26:34,410 --> 00:26:38,253
First thing we want to do is to ignore
all buckets whose ending timestamp is

350
00:26:38,253 --> 00:26:40,840
earlier than k bits prior
to the current time.

351
00:26:40,840 --> 00:26:44,130
Those buckets are all outside
the range we want to count so

352
00:26:44,130 --> 00:26:45,060
they make no contribution.

353
00:26:47,670 --> 00:26:52,534
Start by summing the sizes of all the
buckets except the oldest bucket that is

354
00:26:52,534 --> 00:26:55,128
still in the range we are interested in.

355
00:26:55,128 --> 00:26:57,111
Then add half the size of that bucket.

356
00:27:00,118 --> 00:27:01,210
Okay.

357
00:27:01,210 --> 00:27:04,790
The reason we only had half the oldest
bucket size is that we really don't know

358
00:27:04,790 --> 00:27:08,059
how many ones from that bucket
are still within the range of interest.

359
00:27:08,059 --> 00:27:14,674
By guessing half, we minimize the maximum
error as we'll discuss on the next slide.

360
00:27:14,674 --> 00:27:17,535
So here is why the estimate
can't be off by a factor of

361
00:27:17,535 --> 00:27:19,690
more than 50% from the true answer.

362
00:27:22,320 --> 00:27:26,795
For a supposed that the oldest bucket in
the range we're interested in has size 2i.

363
00:27:29,480 --> 00:27:30,780
We assumed half, or

364
00:27:30,780 --> 00:27:35,065
2i minus 1 of its 1's are among
the most recent k bits to arrive.

365
00:27:35,065 --> 00:27:38,415
The true number could be
anything between 1 and 2i so

366
00:27:38,415 --> 00:27:41,100
our error is upper bounded by 2i minus 1.

367
00:27:43,882 --> 00:27:46,290
Now what's the smallest
the true answer could be?

368
00:27:47,760 --> 00:27:50,535
There is at least one bucket
of each of the sizes less than

369
00:27:50,535 --> 00:27:54,580
2i that lies completely within the last,
k bits.

370
00:27:55,790 --> 00:28:00,856
These account for at least 1 plus 2

371
00:28:00,856 --> 00:28:05,630
plus 4 plus so on, up to 2i minus 1.

372
00:28:06,772 --> 00:28:14,830
And that's 2 to the,
that sum is 2i minus 1.

373
00:28:14,830 --> 00:28:17,859
Now we add 1 for the 1 that is
at the end of the oldest bucket.

374
00:28:17,859 --> 00:28:20,825
That bucket has an ending
timestamp that's within range.

375
00:28:20,825 --> 00:28:23,359
And buckets always end in a 1 so

376
00:28:23,359 --> 00:28:28,051
there is, there are at least
2i 1's within the range.

377
00:28:32,224 --> 00:28:35,570
Okay, since our error is
no more than 2i minus 1.

378
00:28:35,570 --> 00:28:38,700
That error is at most 50%, you know?

379
00:28:38,700 --> 00:28:41,050
We're not going to discuss
the extensions here but

380
00:28:41,050 --> 00:28:45,120
it is possible to modify the algorithm
described to limit the error to

381
00:28:45,120 --> 00:28:49,380
any fraction we like greater than 0,
while still using only on the order of

382
00:28:49,380 --> 00:28:54,260
log squared N bits to represent all
the buckets we need to represent.

383
00:28:54,260 --> 00:28:56,170
The textbook describes how to do this.