REVIEW 1 cited by
Simple set cardinality estimation through random sampling
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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\big(\sqrt{n} \cdot \epsilon^{-1}\sqrt{\log(\delta^{-1})}\big)$ samples (for $\epsilon^{-1}\sqrt{\log(\delta^{-1})} = O(\sqrt{n})$).
Forward citations
Cited by 1 Pith paper
-
Improved Cardinality Estimation by Learning Queries Containment Rates
Learned containment rates between query pairs, combined with a queries pool of known cardinalities, substantially improve cardinality estimates on multi-join queries.
Discussion (0). Continue with ORCID to comment.