Есть ли эффективный способ уменьшить ошибку в HyperLogLog (Redis)?
В redis мы рассматриваем hyperLogLog как установленный для отдельных элементов.
Как известно, для каждого ключа HLL потребляет только 12 КБ памяти и производит приближения со стандартной ошибкой 0,81%.
Так как у меня есть так много элементов для подсчета. Поэтому здесь я хочу уменьшить количество ошибок, сохраняя элементы в нескольких ключах hll (например, "hll_key_%d" % (Element mod 1024))
Это эффективный способ снизить ошибку на самом деле? Или любой другой способ добиться?
2 ответа
Это зависит. Ошибка HyperLogLogs может считаться нормально распределенной, если количество вставленных элементов значительно больше, чем количество регистров, которое составляет 2^14 в реализации Redis. Если элементы распределены одинаково по нескольким HyperLogLogs, а число элементов в HyperLogLog по-прежнему больше, чем число регистров, общая оценка мощности, полученная путем суммирования оценок мощности всех HyperLogLog, будет иметь меньшую ошибку.
Причина в том, что сумма N независимо и нормально распределенных чисел со средним значением M и стандартной ошибкой 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. Как только частичное количество элементов упадет ниже количества регистров, допущение нормально распределенных ошибок будет нарушено, а улучшение ошибки оценки будет меньшим или даже незначительным.
НЕТ, вы НЕ МОЖЕТЕ уменьшить ошибку, разделив ключи на несколько HyperLogLogs. Независимо от того, сколько HyperLogLogs вы используете, ошибка всегда составляет 0,81%.
Нет способа уменьшить ошибку, если вы не измените исходный код.