Есть ли эффективный способ уменьшить ошибку в HyperLogLog (Redis)?

Question

В redis мы рассматриваем hyperLogLog как набор отдельных элементов.

Как всем известно, для каждого ключа HLL потребляет только 12 КБ памяти и производит приближения со стандартной ошибкой 0,81%

Так как у меня так много элементов для подсчета. Поэтому здесь я хочу уменьшить количество ошибок, сохраняя элементы в нескольких ключах hll (например, "hll_key_% d"% (Element mod 1024))

Это эффективный способ снизить ошибку на самом деле? Или любой другой способ достижения?

Answer 1

Это зависит. Ошибка HyperLogLogs может считаться нормально распределенной, если количество вставленных элементов значительно больше, чем количество регистров, которое составляет 2 ^ 14 в реализации Redis. Если элементы распределены одинаково по нескольким HyperLogLogs, а количество элементов в HyperLogLog по-прежнему превышает число регистров, общая оценка мощности, полученная путем суммирования оценок мощности всех HyperLogLog, будет иметь меньшую ошибку.

Причина в том, что сумма N независимо и нормально распределенных чисел со средним М и стандартной ошибкой S будет нормально распределена со средним N x M и стандартной ошибкой S x SQRT (N). Следовательно, относительная ошибка изменяется от S / M до S x SQRT (N) / (N x M) = S / (M x SQRT (N)), что соответствует улучшению SQRT (N).

Однако этот подход с разделением не будет работать для произвольного числа HyperLogLogs. Как только частичное количество элементов упадет ниже числа регистров, допущение нормально распределенных ошибок будет нарушено, а улучшение ошибки оценки будет меньше или даже незначительным.

Answer 2

НЕТ, вы НЕ МОЖЕТЕ уменьшить ошибку, разделив ключи на несколько HyperLogLogs. Независимо от того, сколько HyperLogLogs вы используете, ошибка всегда составляет 0,81%.

Нет способа уменьшить ошибку, если вы не измените исходный код.