Database Reference
In-Depth Information
4.5.6
Exercises for Section 4.5
EXERCISE
4.5.1 Compute the surprise number (second moment) for the stream 3, 1, 4, 1, 3,
4, 2, 1, 2. What is the third moment of this stream?
!
EXERCISE
4.5.2 If a stream has
n
elements, of which
m
are distinct, what are the minimum
and maximum possible surprise number, as a function of
m
and
n
?
EXERCISE
4.5.3 Suppose we are given the stream of
Exercise 4.5.1
,
to which we apply the
Alon-Matias-Szegedy Algorithm to estimate the surprise number. For each possible value
of
i
, if
X
i
is a variable starting position
i
, what is the value of
X
i
.value
?
EXERCISE
4.5.4 Repeat
Exercise 4.5.3
if the intent of the variables is to compute third mo-
ments. What is the value of each variable at the end? What estimate of the third moment
do you get from each variable? How does the average of these estimates compare with the
true value of the third moment?
EXERCISE
4.5.5 Prove by induction on
m
that 1 + 3 + 5 + · · · + (2
m
− 1) =
m
2
.
EXERCISE
4.5.6 If we wanted to compute fourth moments, how would we convert
X.value
to an estimate of the fourth moment?
4.6 Counting Ones in a Window
We now turn our attention to counting problems for streams. Suppose we have a window
of length
N
on a binary stream. We want at all times to be able to answer queries of the
form “how many 1s are there in the last
k
bits?” for any
k
≤
N
. As in previous sections, we
focus on the situation where we cannot afford to store the entire window. After showing
an approximate algorithm for the binary case, we discuss how this idea can be extended to
summing numbers.
4.6.1
The Cost of Exact Counts
To begin, suppose we want to be able to count exactly the number of 1s in the last
k
bits
for any
k
≤
N
. Then we claim it is necessary to store all
N
bits of the window, as any rep-
resentation that used fewer than
N
bits could not work. In proof, suppose we have a repres-
entation that uses fewer than
N
bits to represent the
N
bits in the window. Since there are
