Приложение к главе 7
Двойной логарифм в HyperLogLog
Хеш-значения – это последовательности из нулей и единиц одинаковой длины. Обозначим длину хеш-значений через т. Тогда получим 2m разных хеш-значений (см. и к ней).
Теперь допустим, что нам нужно сосчитать n различных объектов. Чтобы присвоить им всем разные хеш-значения, понадобится как минимум n хеш-значений, то есть
2m > n или m > log2(n).
Стало быть, m должно быть того же порядка величины, что и log2(n).
Алгоритм К-Minimum Values запоминает К самых маленьких хеш-значений длины m, то есть для этого алгоритма нам нужен объем памяти примерно K log2(n).
HyperLogLog запоминает только максимальное количество нулей в начале хеш-значений. Если сами хеш-значения длины m, то и нулей может быть не больше, чем т. Значит, нам нужно держать в памяти число между 0 и m. Оно тоже записывается с помощью последовательности нулей и единиц. Какой длины должны быть эти последовательности? Если последовательности длины l, то мы можем записать 2l разных чисел. Стало быть, чтобы записать m + 1 разных чисел, должно выполняться
2l = m + 1 или l = log2(m + 1) ≈ log2(m).
В памяти нам нужно держать только l битов информации (последовательность из нулей и единиц длины l). Из предыдущих формул получается:
l ≈ log2 (m) ≈ log2 log2 (n).
Для повышения точности хеш-значения разбивают на r регистров и запоминают максимальное число нулей в каждом регистре отдельно. В результате требуется порядка r log2 (log2 (n)) битов памяти. Относительная точность оценки задается формулой 1,04÷ √r.
