Cardinality Estimation (Cardinality Estimation)

From Algorithm Wiki
Jump to navigation Jump to search


Given a multiset of (possibly hashed) values, estimate the number of distinct elements of the multiset. Of interest is minimizing storage usage.


$N$: number of values in multiset

$n$: cardinality of multiset (not known)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive solution 1940 $O(N)$ $O(n)$ Exact Deterministic
Flajolet–Martin algorithm 1984 $O(N)$ $O(log n)$ Randomized Time & Space
LogLog algorithm 2003 $O(N)$ $O(log(log(n)$)) Randomized Time & Space
HyperLogLog algorithm 2007 $O(N)$ $O(eps^{-2}*log(log(n)$))+log(n)) Randomized Time & Space
HyperLogLog++ 2014 $O(N)$ $O(eps^{-2}*log(log(n)$))+log(n)) Randomized Time

Time Complexity Graph

Cardinality Estimation - Time.png