HyperLogLog
Probabilistische datastructuur die het aantal unieke elementen in een stroom telt met constant geheugengebruik (Flajolet e.a., 2007). Met 12 KB zijn miljarden unieke items te tellen met circa 2% afwijking.
De truc: hash de sleutels, tel de voorloopnullen in de binaire hash. De langste reeks zegt iets over hoeveel unieke waarden er voorbijkwamen (meer unieke waarden betekent meer kans op een lange reeks nullen). De mediaan over m “emmers” verkleint de variantie.
Zit achter Redis PFCOUNT en de benaderde distinct-tellingen van Presto/Trino, BigQuery en Druid. Winst ten opzichte van exact tellen met count(distinct): van MB’s geheugen per query naar KB’s, en de resultaten zijn te mergen over partities.