Simple set cardinality estimation through random sampling

Abstract

We present a simple algorithm that estimates the cardinality $n$ of a set $V$ when allowed to sample elements of $V$ uniformly and independently at random. Our algorithm with probability $(1-\delta )$ returns a $(1\pm \epsilon )-$approximation of $n$ drawing $O(\sqrt{n}\cdot {\epsilon }^{-1}\sqrt{\log ({\delta }^{-1})})$ samples (for ${\epsilon }^{-1}\sqrt{\log ({\delta }^{-1})}=O(\sqrt{n})$).

3 pages

Cited by in corpus (3)

• Improved Cardinality Estimation by Learning Queries Containment Rates
• NN-based Transformation of Any SQL Cardinality Estimator for Handling DISTINCT, AND, OR and NOT
• On the Complexity of Sampling Nodes Uniformly from a Graph