HyperLogLog

Info

HyperLogLog (HLL) - это алгоритм, используемый для оценки количества уникальных элементов в большом наборе данных. Он был разработан Ларрисом МакКарти и Энди Кнутом и является одним из примеров вероятностных структур данных.

HyperLogLog использует хэш-функции для оценки количества уникальных элементов без необходимости хранить сами элементы. Он работает путем разделения входных данных на несколько "гиперлогических регистров" (HyperLogLog registers), каждый из которых представляет собой битовую строку.

Основная идея алгоритма заключается в том, что для каждого элемента в наборе данных вычисляется хэш-значение, а затем определяется длина нулевой последовательности в начале хэша (так называемый "ранг" или "leading zeros count"). Этот ранг используется для обновления гиперлогического регистра, который соответствует этому элементу.

HyperLogLog имеет высокую точность для небольших наборов данных и может быть использован для анализа больших данных, таких как веб-аналитика, анализ социальных сетей и другие приложения, где необходимо оценить количество уникальных элементов.

Однако, важно отметить, что хотя HyperLogLog обеспечивает высокую точность для небольших наборов данных, он не гарантирует точность для больших наборов данных.

Для больших наборов данных может потребоваться использование алгоритмов, которые обеспечивают более точные оценки, таких как алгоритмы, основанные на линейном сканировании.

Где используется?

Presto и многие другие движки для обработки больших объёмов данных используют HyperLogLog для примерной оценки количества элементов, что требует гораздо меньше памяти по сравнению с COUNT(DISTINCT).