$L_0$ estimation, not in a stream

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 http://en.wikipedia.org/wiki/Good%E2%80%93Turing_frequency_estimation but that seems rather older than I was expecting.

-
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.

-
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