Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the current state of the art for $L_0$ estimation when not in a stream? I assume that the total number of (not necessarily distinct) objects is very large so you can only see a sample of them.

I found but that seems rather older than I was expecting.

share|cite|improve this question
Good-Turing estimation does more though: it estimates the frequencies of items. It sounds like you only want the number of distinct items. – Suresh Venkat Feb 21 '13 at 20:06
@SureshVenkat Yes you are right. – motl7 Feb 21 '13 at 23:06

For sampling-based algorithms, nearly tight upper and lower bounds are known for the query complexity of estimating the number of distinct elements in a sequence.

Charikar, Chowdhuri, Motwani and Narsayya showed that multiplicative approximation of the number of distinct elements to within a factor $\alpha$ can be achieved with $q= O(n/\alpha^2)$ queries into the sequence.

Here's the algorithm. Sample $q$ items uniformly at random from the sequence. Let $d$ be the number of distinct items in the sample, and let $f_1$ be the number of items that appear exactly once in the sample. Then, output $d + \sqrt{n/q} \cdot f_1$.

The analysis is also very clean. Assume without loss of generality that each element in the sequence is an integer in $[k]$, where $k$ is the number of distinct elements. Let $p_i$ be the probability of selecting $i$ when sampling uniformly from the sequence. Then, the expected output of the estimator is:

$$\mathbb{E}[d + \sqrt{n/q}\cdot f_1] = \sum_{i=1}^k (1 - (1-p_i)^q) + \sqrt{n/q} \cdot p_i q (1-p_i)^{q-1}$$

Now, the point is that for any valid $p_i$, the value inside the summation is between $\Omega(\sqrt{q/n})$ and $O(\sqrt{n/q})$. (This uses the fact that $1/n \leq p_i < 1$.) So, the expected output of the algorithm is within $O(\sqrt{n/q})$ of $k$.

Charikar et al.'s estimator can also be used to get an additive approximation of the number of distinct elements. One can estimate the number of distinct elements upto $\pm \beta n$ by making $O((1-2\beta) n)$ samples. This was the state-of-the-art for a long while until STOC '11 when Greg and Paul Valiant showed that it's possible to reduce the sample complexity and time complexity to $O(\frac{n}{\beta^2 \log n})$. Their algorithm is based on a very general result that, given a probability distribution $D$, constructs a distribution $D'$ using $O(n/\log n)$ samples such that $D$ and $D'$ are close to each other in relative earthmover distance. So, one can make sure that the support size of $D'$ and the support size of $D$ are only an additive $\beta n$ away from each other.

As for lower bounds, Charikar et al. showed that for $\alpha$-multiplicative approximation, $\Omega(n/\alpha^2)$ queries are needed. The proof stems from the observation that $\Omega(n/\alpha^2)$ queries are needed to distinguish $n$ identical items from the same sequence with $\alpha^2$ unique elements inserted in random locations. For additive approximation, however, this bound is sort of trivial; for constant $\beta$, this would only give a constant lower bound on the query complexity. Raskhodnikova, Ron, Shpilka, and Smith showed a nearly linear bound even for additive approximation. Specifically, they prove that estimating to within additive error $n/23$ requires $n/2^{\sqrt{\log n} \log \log n}$ queries. The Valiants in their above-cited paper showed a lower bound of $\Omega(n/\log n)$ for estimating to any additive error less than $n/4$, implying that their upper-bound is tight upto constant factors.

share|cite|improve this answer
Thanks very much. I suppose if you are worried about worst case input distributions and guaranteed bounds that is what you get. What about MLEs or biased estimators or if you have some useful prior? – motl7 Feb 22 '13 at 8:51
You should take a look at the paper by Charikar et al. There, they discuss other heuristic estimators that do well in practice and that adapt to the input distribution. There is also this paper by Motwani and Vassilvitskii that gives an estimator for the case when the data is drawn from a power law distribution. In this case, their sample complexity grows only with the number of distinct elements and not with $n$ ! – arnab Feb 22 '13 at 21:14
Thanks very much. – motl7 Feb 23 '13 at 15:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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