Counting

This algorithm approximates the number of unique items (cardinality) of a multiset. This is achieved by using a hash function that is applied to every element that is to be counted. The algorithm observes the maximum number of leading zeros that occur for all hash values, where intuitively hash values with more leading zeros are less likely and indicate a larger cardinality.

Inputs

Insert 1,000,000 random records with a given cardinality of...

Precision

Smaller will give a worse estimate

less error, more memory → ←greater error, less memory

Result

Estimate ( $E$ )	NaN (NaN% error)
Registers ( $m$ )		The number of registers used.
Memory used	NaN	bytes

Calculation

The cardinality ( $E$ ) is estimated by the formula $a_m m^2 Z$

$a_m$		A constant used to correct a systematic multiplicative bias
$m^2$	NaN	The number of registers ( $m$ ) squared
$Z$		The harmonic mean of the registers