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