HyperLogLogバケットサイズ制限

Question

HyperLogLogでは、32ビットハッシュデータのバケットサイズは4〜16ビットにする必要があります。これにより、誤差が1.04/sqrt（m）のm = 16,32,64、...、65536になります。 M = 2 ^（バケットサイズ）。

この範囲でmを選択する理由は何ですか？

レジスタ配列のメモリ使用量とゼロからの誤差の収束のため、このように選択しますか？

Answer 1

原則として、Hyperloglogアルゴリズムは、2の累乗である任意の数のバケットに対して機能します。ただし、ほとんどの実装ではいくつかの制限が加えられます。バケットサイズは通常5〜8ビットで、実装にも依存します。