Cardinality Estimation

Description

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)

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

Space Complexity graph

Pareto Decades graph