HyperLogLog

HyperLogLog - это алгоритм для решения проблемы подсчета различных элементов, аппроксимирующий количество отдельных элементов в мультимножестве . ^{[1] Для} вычисления точной мощности мультимножества требуется объем памяти, пропорциональный мощности, что непрактично для очень больших наборов данных. Вероятностные оценки мощности, такие как алгоритм HyperLogLog, используют значительно меньше памяти, чем это, за счет получения только приблизительного значения мощности. Алгоритм HyperLogLog может оценивать мощности> 10 ⁹ с типичной точностью (стандартной ошибкой) 2%, используя 1,5 КБ памяти. ^[1] HyperLogLog - это расширение более раннего алгоритма LogLog,^[2] происходит от алгоритма Флажоле – Мартина 1984 года. ^[3]

Терминология [ править ]

В оригинальной статье Flajolet et al. ^[1] и в соответствующей литературе, посвященной проблеме подсчета различных элементов, термин «количество элементов» используется для обозначения количества отдельных элементов в потоке данных с повторяющимися элементами. Однако в теории мультимножеств термин относится к сумме кратностей каждого члена мультимножества. В этой статье используется определение Флажолета для согласованности с источниками.

Алгоритм [ править ]

В этот раздел включен список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить этот раздел, добавив более точные цитаты. ( Март 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

В основе алгоритма HyperLogLog лежит наблюдение, что мощность мультимножества равномерно распределенных случайных чисел может быть оценена путем вычисления максимального количества ведущих нулей в двоичном представлении каждого числа в наборе. Если максимальное количество наблюдаемых начальных нулей равно  n , оценка количества различных элементов в наборе равна 2 ⁿ . ^[1]

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

Недостатком простой оценки мощности, полученной с помощью описанного выше алгоритма, является большая дисперсия . В алгоритме HyperLogLog дисперсия минимизируется путем разделения мультимножества на многочисленные подмножества, вычисления максимального количества ведущих нулей в числах в каждом из этих подмножеств и использования гармонического среднего для объединения этих оценок для каждого подмножества в оценку мощность всего множества. ^[4]

Операции [ править ]

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

Данные HyperLogLog хранятся в массиве M счетчиков, называемых регистрами с размером m , которые в исходном состоянии установлены в 0.

Добавить [ редактировать ]

Операция добавления состоит из вычисления хэша входных данных V с хэш - функцией ч , получая первый б биты (где Ь есть ), и добавление 1 к ним , чтобы получить адрес регистра изменить. С оставшимися битами вычисляется, которое возвращает позицию крайнего левого 1. Новое значение регистра будет максимальным между текущим значением регистра и .${\ textstyle \ log _ {2} (м)}$${\ textstyle \ rho (ш)}$${\ textstyle \ rho (ш)}$

${\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b}\rangle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j],\rho (w))\\\end{aligned}}}$

Подсчитать [ править ]

Алгоритм подсчета состоит в вычислении гармонического среднего для m регистров и использовании константы для получения оценки подсчета:${\textstyle E}$

${\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}$

${\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}}$

${\displaystyle E=\alpha _{m}m^{2}Z}$

Интуиция подсказывает, что n - неизвестная мощность M , и каждое подмножество будет иметь элементы. Тогда должно быть близко к . Среднее гармоническое значение 2 для этих величин должно быть близко . Таким образом, должно быть примерно n .${\textstyle M_{j}}$${\textstyle n/m}$${\textstyle \max _{x\in M_{j}}\rho (x)}$${\textstyle \log _{2}(n/m)}$${\textstyle mZ}$${\textstyle n/m}$${\textstyle m^{2}Z}$

Наконец, постоянная вводится для исправления систематического мультипликативного смещения, возникающего из-за хеш-коллизий.${\textstyle \alpha _{m}}$${\textstyle m^{2}Z}$

Практические соображения [ править ]

Константу непросто вычислить, и ее можно аппроксимировать формулой ^[1]${\textstyle \alpha _{m}}$

${\displaystyle \alpha _{m}\approx {\begin{cases}m=16&0.673\\m=32&0.697\\m=64&0.709\\m\geq 128&{\frac {0.7213}{1+{\frac {1.079}{m}}}}\end{cases}}}$

Однако метод HyperLogLog смещен для малых мощностей ниже порогового значения . В исходной статье предлагается использовать другой алгоритм для малых мощностей, известный как линейный счет. ^[5] В случае, когда приведенная выше оценка меньше порогового значения , можно использовать альтернативный расчет:${\textstyle {\frac {5}{2}}m}$${\textstyle E<{\frac {5}{2}}m}$

1. Пусть будет количество регистров, равное 0.${\textstyle V}$
2. Если , используйте стандартный оценщик HyperLogLog, описанный выше.${\textstyle V=0}$${\textstyle E}$
3. В противном случае используйте линейный счет: ${\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}$

Кроме того, для очень больших мощностей, приближающихся к пределу размера регистров ( для 32-битных регистров), мощность можно оценить с помощью:${\textstyle E>{\frac {2^{32}}{30}}}$

${\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}}\right)}$

С учетом приведенных выше поправок для нижней и верхней границ ошибку можно оценить как .${\textstyle \sigma =1.04/{\sqrt {m}}}$

Объединить [ править ]

Операция слияния двух HLL ( ) заключается в получении максимума для каждой пары регистров${\textstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2}}$${\textstyle j:1..m}$

${\displaystyle {\mathit {hll}}_{\text{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}$

Сложность [ править ]

Для анализа сложности используется модель потоковой передачи данных ^[6] , которая анализирует пространство, необходимое для получения приближения с фиксированной вероятностью успеха . Относительная ошибка HLL равна, и ему нужно место, где n - установленная мощность, а m - количество регистров (обычно меньше одного байта).${\displaystyle (\epsilon ,\delta )}$${\displaystyle 1\pm \epsilon }$${\displaystyle 1-\delta }$${\displaystyle 1.04/{\sqrt {m}}}$${\displaystyle O(\epsilon ^{-2}\log \log n+\log n)}$

Операция добавления зависит от размера вывода хеш-функции. Поскольку этот размер фиксирован, мы можем считать время выполнения операции добавления равным .${\displaystyle O(1)}$

В счетах и слияние операции зависят от количества регистров м и имеют теоретическую стоимость . В некоторых реализациях ( Redis ) ^[7] количество регистров фиксировано, а стоимость указана в документации.${\displaystyle O(m)}$${\displaystyle O(1)}$

HLL ++ [ править ]

Алгоритм HyperLogLog ++ предлагает несколько улучшений в алгоритме HyperLogLog для уменьшения требований к памяти и повышения точности в некоторых диапазонах мощности: ^[6]

• 64-битная хеш-функция используется вместо 32-битной, использованной в исходной статье. Это уменьшает хэш-коллизии для больших мощностей, что позволяет убрать поправку на большой диапазон.
• Некоторое смещение обнаружено для малых мощностей при переходе от линейного счета к счету HLL. Для смягчения проблемы предлагается коррекция эмпирического смещения.
• Разреженное представление регистров предлагается для уменьшения требований к памяти для малых мощностей, которые позже могут быть преобразованы в плотное представление, если количество элементов растет.

Потоковое HLL [ править ]

Когда данные поступают в одном потоке, историческая обратная вероятность или оценка мартингейла ^{[8] [9]} значительно повышает точность скетча HLL и использует на 36% меньше памяти для достижения заданного уровня ошибок. Этот оценщик является оптимальным для любого дублирующего нечувствительного приблизительного отдельного счетного эскиза в одном потоке.

Сценарий с одним потоком также приводит к вариантам построения эскиза HLL. HLL-TailCut + использует на 45% меньше памяти, чем исходный эскиз HLL, но за счет зависимости от порядка вставки данных и невозможности объединить эскизы. ^[10]

Ссылки [ править ]

• «Вероятностные структуры данных для веб-аналитики и интеллектуального анализа данных | Высокомасштабируемый блог» . highscalable.wordpress.com. Май 2012 . Проверено 19 апреля 2014 .
• «Новые алгоритмы оценки мощности для скетчей HyperLogLog» (PDF) . Проверено 29 октября 2016 .