「data-structures」の記事

HyperLogLog：調和平均で異なる要素の数を推定する仕組みと1.04/√m誤差の前提

2007年のFlajoletらの原論文に基づき、HyperLogLogがレジスタ番号jとρで異なる要素の数を推定する方法、調和平均を使う理由、小範囲・大範囲の補正、1.04/√mの誤差が前提とする条件を整理します。