Question
Suppose we are executing the DGIM algorithm for approximate counting of bits in a stream. Let the window size be 1000.
(a) What is the largest possible bucket size in the representation of this stream?
(b) Suppose each of the last 1000 bits is 1. What is the smallest possible size of the largest bucket in the representation of the window?
(a) What is the largest possible bucket size in the representation of this stream?
(b) Suppose each of the last 1000 bits is 1. What is the smallest possible size of the largest bucket in the representation of the window?
Answers
rouba
256