Google 的 HyperLogLog++

算是接續昨天寫的「Redis 對 HyperLogLog 省空間的實作」,在 RedisHyperLogLog 實作有提到 Google 在 2013 年的論文「HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm」,裡面提出了 HyperLogLog++ (HLL++)。

論文中 Google 提出來的改進主要有三個,第一個是用了 64-bit hash function:

5.1 Using a 64 Bit Hash Function

原因也有提到,當需要處理超過十億筆資料時,32-bit hash 的 4B 上限就有點不太夠用:

To fulfill the requirement of being able to estimate multisets of cardinalities beyond 1 billion, we use a 64 bit hash function.

這點也簡化了原始論文中當 cardinality 接近 232 時的 count 估算修正,因為實務上不太可能遇到 264 上限?

It would be possible to introduce a similar correction if the cardinality
approaches 264, but it seems unlikely that such cardinalities are encountered in practice.

第二個是改善 cardinality 比較低時的 count 估算公式:

5.2 Estimating Small Cardinalities

第三個則是提出了 sparse representation 的概念,在 cardinality 比較低的時候不需要直接用完整的 HLL 資料結構儲存:

5.3 Sparse Representation

另外也是一路往回讀的關係,查資料才了解 (ε, δ)-model 的用法,在「A Quick Introduction to Data Stream Algorithmics」這邊投影片的 Page 17 可以看到指的是,有多少正確性 (randomized) 是給出 ε 內的誤差 (approximation),像是 Page 18 的範例:

Example: Actual answer is within 5 ± 1 with prob ≥ 0.9

HyperLogLog 與 Bloom Filter

看到 FacebookPresto 裡增加使用 HyperLogLog 計算數量的能力,突然想到常常忘記這兩個拿準確度換速度的資料結構:「HyperLogLog in Presto: A significantly faster way to handle cardinality estimation」。

HyperLogLog (HLL) 是解決 Count-distinct problem 的資料結構,用很少的記憶體就可以給出一個誤差不大的值 (用 1.5KB 的空間處理十億等級的資料,誤差大約在 2%),所以 Presto 利用這個資料結構引進了 APPROX_DISTINCT() 以及其他的函數,就很容易在 L2/L3 cache 裡運算,藉此大幅提昇速度。

Depending upon the problem at hand, we can achieve speed improvements of anywhere from 7x to 1,000x.

先前也提過 Reddit 也用 HLL 統計資料:「Reddit 在處理 Page View 的方式」。

Bloom Filter 也是在處理大量資料的問題,但這個資料結構的功能不太一樣,是給出「有沒有存在」,使用空間與誤差大約是 10 bits per key (1% false positive),另外先前也有提到一些變形,可以提供其他功能。像是「Quotient filter」與「Cuckoo Filter:比 Bloom Filter 多了 Delete」。