Simple set cardinality estimation through random sampling

2015/12/24 by Marco Bressan, Bressan, Marco, Enoch Peserico +3 · 3 citations
Computer Science · #Machine Learning and Algorithms #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1512.07901

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-δ) returns a (1±ε)-approximation of n drawing O(√(n) ⋅ ε^-1√log(δ^-1)) samples (for ε^-1√log(δ^-1) = O(√(n))).

Cited by

• 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

Related

• Cardinality Estimation Meets Good-Turing
• Q-error Bounds of Random Uniform Sampling for Cardinality Estimation
• The Distance Approach to Approximate Combinatorial Counting
• Detecting random sets by samplings from their values
• Counting random k-SAT near the satisfiability threshold