Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
Authors:
- Sofya RaskhodnikovaSRSofya Raskhodnikova
- Dana RonDRDana Ron
- Amir ShpilkaASAmir Shpilka
- Adam SmithASAdam Smith
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (3) , 813-842
Abstract
We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least $\frac{1}{n}$. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. Charikar, Chaudhuri, Motwani, and Narasayya [in Proceedings of the Nineteenth ACM SIGMOD–SIGACT–SIGART Symposium on Principles of Database Systems, 2000, pp. 268–279] and Bar-Yossef, Kumar, and Sivakumar [in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2001, pp. 266–275] proved that multiplicative approximation for these problems within a factor $\alpha>1$ requires $\Theta(\frac{n}{\alpha^2})$ queries to the input sequence. Their lower bound applies only when the number of distinct elements (or the support size of a distribution) is very small. For both problems, we prove a nearly linear in n lower bound on the query complexity, applicable even when the number of distinct elements is large (up to linear in n) and even for approximation with additive error. At the heart of the lower bound is a construction of two positive integer random variables, $\mathsf{X}_1$ and $\mathsf{X}_2$, with very different expectations and the following condition on the first k moments: $\mathsf{E}[\mathsf{X}_1]/\mathsf{E}[\mathsf{X}_2] = \mathsf{E}[\mathsf{X}_1^2]/\mathsf{E}[\mathsf{X}_2^2] = \cdots = \mathsf{E}[\mathsf{X}_1^k]/\E[\mathsf{X}_2^k]$. It is related to a well-studied mathematical question, the truncated Hamburger problem, but differs in the requirement that our random variables have to be supported on integers. Our lower bound method is also applicable to other problems and, in particular, gives a new lower bound for the sample complexity of approximating the entropy of a distribution.
Keywords
This publication has 19 references indexed in Scilit:
- Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem2007
- Sublinear Algorithms for Approximating String CompressibilityLecture Notes in Computer Science, 2007
- The Complexity of Approximating the EntropySIAM Journal on Computing, 2005
- All of Statistics2004
- Counting Distinct Elements in a Data Stream2002
- Average Case Analysis of Algorithms on Sequences2001
- Bounds for the total variation distance between the binomial and the Poisson distribution in case of medium-sized success probabilitiesJournal of Applied Probability, 1999
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977