Bloom filter je pravděpodobnostní struktura, která nám umožňuje s jistou mírou pravděpodobnosti říci, zda se nějaký prvek x nachází v množině M.

Ukážeme si, jak efektivně použít HyperLogLog k tomu, abychom spočítali počet unikátních návštěv pro nějaký web za různá časová období, a to včetně různých zpřesňujících údajů, jako je použitý prohlížeč, OS a podobně. Jednou z výhod algoritmu HyperLogLog totiž je, že můžeme bez ztráty informace sjednotit vektory, které drží maxima. Jinými slovy, pokud přes HyperLogLog spočítáme počet unikátních uživatelů v sobotu a pak v neděli, můžeme snadno spočítat počet unikátních uživatelů o víkendu.

Série o algoritmech na odhadování počtu unikátních hodnot v multimnožině pokračuje článkem o state of the art algoritmu HyperLogLog. Nicméně veškeré myšlenky, které stojí za tímto algoritmem vychází z dříve popsaného LogLogu, takže pokud chcete číst dál, ujistěte se, že znáte dobře LogLog.

Po předchozích dílech o Linear Countingu a Min Value se konečně dostáváme ke skoro nejvíc nejlepšímu pravděpodobnostnímu algoritmu na odhadování počtu unikátních hodnot v sadě dat, LogLogu. Lepší už je jen jeho bratříček HyperLogLog, který z LogLogu vychází, ale o něm zase příště.

V minulém článku o Linear Countingu jsme si probrali základní algoritmy na výpočet a odhad počtu unikátních hodnot v nějaké sadě dat. Dnes náš čeká další pravděpodobností algoritmus, který umožňuje se slušnou přesností a malými paměťovými nároky odhadnout počet unikátů.

Jak bychom mohli spočítat počet unikátních hodnot v nějaké sadě dat, pokud by těchto dat bylo opravdu hodně? Můžeme mít například službu, která měří počet unikátních uživatelů na nějakém velkém webu nebo klidně na celé .cz/.com/.whatever doméně či tak něco.