Flajolet analyzed Wegman's Adaptive Sampling for estimating distinct values (species) in a stream (population), giving an unbiased estimator for mean and specified the standard error to be approximately $1.2/\sqrt(n)$ where n is the number of samples. Another way of estimating the number of distinct values is by using Bernoulli sampling over uniformly hashed value of the target attribute. In this case, the standard error should be $\sqrt{pq/n}$. The obvious advantage of Adaptive Sampling is the number of samples retained is at most n whereas Bernoulli sampling would require $Np$ samples ($O(N)$ in $N$, the actual number of distinct values). Is my analysis correct? For some reason, I cannot accept the Bernoulli sampling can be more accurate than Adaptive for fixed sample size, $n$. Thoughts?


I do not quite understand the question because you do not define some of your paremters (what are $p$ and $q$?). But let me try to clarify things. Let $N$ be the true number of distinct items.

First Flajolet's guarantee for Wegman's algorithm is that, if the space used is $n$ words, then the estimate $X$ produced by the algorithm satisfies $$ \sqrt{\mathbb{E}[(X - N)^2]} \leq \frac{1.2}{\sqrt{n}}N. $$

Your suggestion is to sample at a rate $p$ from the $N$ different distinct items. I.e., you make a pass over the sequence of item identifiers and you keep each identifier in memory with probability $p$. Let the number of items stored in memory be $n$. Then the expected value of $n$ is $pN$, and the variance of $n$ is $p(1-p)N$, so we have $$ \sqrt{\mathbb{E}\left[\left(\frac{n}{p}-N\right)^2\right]} =\sqrt{\frac{1-p}{pN}}N = \sqrt{\frac{1-p}{\mathbb{E}[n]}}N. $$

So you are right that this is in some sense comparable with the guarantees for adaptive sampling (as well as those for the Flajolet-Martin probabilistic counting algorithm). However, the issue is that without knowing $N$, you do not know ahead of time what your space complexity $n$ will be, even in expectation. Or to put it another way, you do not know what to set $p$ to in order to make the space complexity acceptable.

A natural fix is to start with some sample rate $p$, say $p = 1$, and once your memory fills up, you lower $p$. This is essentially the adaptive sampling algorithm.

The simple sampling algorithm you suggest can be useful to refine a rough estimate of $N$. For example, you can use adaptive sampling or Flajolet-Martin to get a constant factor approximation to $N$, and then use that approximation to set $p$ in the Bernoulli sampling strategy. See this nice paper by Daniel Kane, Jelani Nelson, and David Woodruff, where they use this idea and a lot more to get an optimal space algorithm for the distinct items problem. The paper also gives references to much of the more important work on this problem.

  • $\begingroup$ Thanks for clarifying. The Kane-Woodruff estimator is very similar to Hyperloglog in that it minimizes the information maintained to estimate distinct values count. The advantage of Bernoulli/Adaptive sampling is that they retain actual sampling (of, e.g., unique users and their attributes). Adaptive sampling seems akin to reservoir sampling (which would require O(N) memory to keep a uniformly random sample of distinct users). $\endgroup$ – user3113353 Dec 25 '13 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.