database - 有什么有效的方法可以减少 HyperLogLog ( redis ) 中的错误？

Question

在 redis 中，我们将 hyperLogLog 设置为不同的元素。

众所周知，对于每个 key ，HLL 仅消耗 12kb 内存并产生标准误差为 0.81% 的近似值

因为我有太多要计算的元素。所以在这里我想通过将元素存储到多个 hll 键中来降低错误发生率(例如 "hll_key_%d"% (Element mod 1024) )

这实际上是降低错误的有效方法吗？或者其他什么方式实现？

Answer 1

这取决于。如果插入元素的数量明显大于 Redis 实现中的寄存器数量(2^14)，则可以假设 HyperLogLogs 的错误呈正态分布。如果元素被平均分片到多个 HyperLogLog 上，并且每个 HyperLogLog 的元素数量仍然大于寄存器数量，则通过对所有 HyperLogLog 的基数估计求和得到的总基数估计将有更小的误差。

原因是平均数 M 和标准误差 S 的 N 个独立且正态分布的数字之和将服从平均数 N x M 和标准误差 S x SQRT(N) 的正态分布。因此，相对误差从 S/M 变为 S x SQRT(N)/(N x M) = S/(M x SQRT(N))，这对应于 SQRT(N) 的改进。

但是，这种分片方法不适用于任意数量的 HyperLogLog。一旦部分基数下降到寄存器数量以下，就会违反正态分布误差的假设，并且估计误差的改进将更小甚至可以忽略不计。