to better cardinality estimates for intersections [@Ting2016].

HyperLogLog Data Structure {#sec:hyperloglog_data_structure}
==========================

$\langle \symBitRepA_1, \ldots, \symBitRepA_\symPrecision,\symBitRepB_1,\ldots,\symBitRepB_\symRegRange\rangle_2 \gets$ $(\symPrecision + \symRegRange)$-bit hash value of $\symDataItem$ $\symIndexI \gets 1+ \langle \symBitRepA_1, \ldots, \symBitRepA_\symPrecision\rangle_2$ $\symRegVal \gets \min(\{\symS\mid \symBitRepB_\symS = 1\}\cup {\{\symRegRange+1\}} )$ $\symRegValVariate_\symIndexI \gets\symRegVal$

The algorithm collects information of incoming elements into a very compact sketching data structure, that finally allows to estimate the number of distinct elements. The data structure consists of $\symNumReg = 2^\symPrecision$ registers. All registers start with zero initial value. The insertion of a data element into a data structure requires the calculation of a $(\symPrecision+\symRegRange)$-bit hash value. The leading $\symPrecision$ bits of the hash value are used to select one of the $2^\symPrecision$ registers. Among the next following $\symRegRange$ bits, the position of the first 1-bit is determined which is a value in the range $[1,\symRegRange+1]$. The value $\symRegRange+1$ is used, if all $\symRegRange$ bits are zeros. If the position of the first 1-bit exceeds the current value of the selected register, the register value is replaced. The complete update procedure is shown in \[alg:insert\].

A sketch can be characterized by the parameter pair $(\symPrecision, \symRegRange)$ where the precision parameter $\symPrecision$ controls the relative estimation error which scales 