Cardinality Estimation

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

Parameters

$N$ : number of values in multiset
$n$ : cardinality of multiset (not known)

Related Problems

Cardinality Estimation

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 5 of 5 algorithms

				See more
HyperLogLog++	2014	$O(N)$	$O(\epsilon^{-2}\log(\log n))+\log n)$
HyperLogLog algorithm	2007	$O(N)$	$O(\epsilon^{-2}\log(\log n))+\log n)$
LogLog algorithm	2003	$O(N)$	$O(\log \log n)$
Flajolet–Martin algorithm	1984	$O(N)$	$O(\log n)$
Naive solution	1940	$O(N)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table