hyperloglog

HyperLogLog 是一种计算近似基数计数（cardinality counting）的算法，用于解决统计唯一元素个数的问题（DISTINCT COUNT）。计算集合的确切基数需要与基数成比例的内存量，这对超大数据集来说是不切实际的。概率基数估计在理论误差范围内计算近似基数，其使用的内存要少得多，如 HyperLogLog 算法能够用 1.5kB 的内存估计大于 10^9 量级的基数，标准误差小于 2%。 HyperLogLog 是早期 LogLog 算法的扩展，LogLog 则是基于 1984 年的 Flajolet-Martin 算法发展而来。先来简单了解一下这三种算法。 Flajolet-Martin Flajolet-Martin 算法的基本思想是利用随机化和位运算来估计唯一元素的基数。对数据集中的每个元素进行哈希映射，将元素映射为一个二进制编码。对每个哈希映射值，找到其二进制编码中从右向左的尾部连续零的个数 len，取 R 为 len 的最大值，估算基数值的公式: 2^R / ϕ (ϕ ≈ 0.77351)。 我们生成值域为 [0, 63] 之间的 8 个随机哈希值用作演示: postgres=# select (random() * 64)::int::bit(6) from generate_series(0,7) order by 1; bit -------- 000110 001001 010000 011101 011110 101010 110101 111010 (8 rows) 按照 Flajolet-Martin 算法计算估算的 Cardinality: R = 4 Cardinality: 2^4 / 0....