HyperLogLog ist ein Algorithmus zur Schätzung der Kardinalität in Datenbanksystemen. Hierbei wird der Algorithmus verwendet, um mittels Mengen und Werten die Beziehungen und Korrelationen zwischen Entitäten festzulegen.
Google verwendet den HyperLogLog Algorithmus laut dem Patent 11,341,147 selbst, um die Korrelation einzelner Entitäten im Suchindex zu bestimmen und eine entsprechende Gewichtung auf einzelne Begriffe zu setzen.
Der HyperLogLog-Algorithmus wird nach eigenen Angaben auch von Amazon Redshift verwendet: https://docs.aws.amazon.com/de_de/redshift/latest/dg/hyperloglog-overview.html
In der Original-Abstraktion von Google heißt es:
Cardinality estimation has a wide range of applications and is of particular importance in database systems. Various algorithms have been proposed in the past, and the HyperLogLog algorithm is one of them. In this paper, we present a series of improvements to this algorithm that reduce its memory requirements and significantly increase its accuracy for an important range of cardinalities. We have implemented our proposed algorithm for a system at Google and evaluated it empirically, comparing it to the original HyperLogLog algorithm. Like HyperLogLog, our improved algorithm parallelizes perfectly and computes the cardinality estimate in a single pass.