Consider a slight modification to the Bottom- k estimator as follows. Suppose we already have a coarse estimation of d (number of distinct elements in the stream): we are given some r satisfying dr100d. Then, our sketch stores all distinct elements x whose hash function value is h(x)[0,], for =k/r and where k=C/2 for C large enough constant. The new estimator is now d=X/, where X is the number of items stored as above. (You can assume that d,r are large enough so that