Участник:Warmte — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «1.»)
 
Строка 1: Строка 1:
1.
+
'''HyperLogLog''' {{---}} это вероятностный алгоритм, оценивающий количество различных элементов в больших потоках данных. Является стриминговым алгоритмом (англ. [[wikipedia:en:Streaming_algorithm|streaming algorithm]]), то есть обрабатывает последовательно поступающие данные в один проход.
 +
 
 +
Подобные алгоритмы используются в тех случаях, когда объемы обрабатываемых данных настолько велики, что получение точного ответа затребует пропорционально слишком большого объёма памяти, в то время как вероятностный алгоритм может дать близкий к точному ответ, будучи с точки зрения памяти намного более оптимальным.
 +
 
 +
==Точность==
 +
 
 +
При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{m}}</tex>, то есть при оценке данных > 10<sup>9</sup> этому алгоритму потребуется всего 1.5 kB памяти для получения ответа с точностью 2%.
 +
 
 +
Предыдущий алгоритм '''LogLog''', использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.
 +
 
 +
==Идея алгоритма==
 +
В основе алгоритма '''HyperLogLog''' лежит наблюдение, что мощность набора равномерно распределенных случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>.
 +
 
 +
Суть алгоритма заключается в следующем: к каждому элемента исходного набора применяется хеш-функция для получения набора равномерно распределенных случайных чисел с той же мощностью, что и исходный набор. Затем мощность этого случайно распределенного набора оценивается с помощью описанного выше алгоритма.
 +
 
 +
Но при таком подходе могут возникать различные проблемы за счёт большой дисперсии получаемой величины, а также некоторых крайних случаев: к примеру, если хэш некоторого элемента будет равен <tex>0</tex>, то максимальное количество ведущих нулей сразу станет равным <tex>log_2{m}</tex>, где <tex>m</tex> {{---}} максимальное значение выбранной хэш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на <tex>2^r</tex> корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.
 +
 
 +
==Описание алгоритма==
 +
*<tex>\mathcal{M}</tex> {{---}} исходный набор элементов <tex>a_1 ... a_n</tex>.
 +
 
 +
*<tex>h : \mathcal{U} \to {0, 1 ... 2^k - 1}</tex> {{---}} выбранная хэш-функция с возможными значениями от <tex>0</tex> до <tex>m - 1</tex>, <tex>k = log_2{m}</tex>.
 +
 
 +
*<tex>r</tex> {{---}} количество бит исходного хэша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.
 +
 
 +
*<tex>z_j</tex> {{---}} максимальное наблюдаемое количество начальных нулей в корзине под номером <tex>j</tex>.
 +
 
 +
Разобьём исходный набор <tex>\mathcal{M}</tex> на наборы <tex>\mathcal{M}_0..\mathcal{M}_{2^r - 1}</tex> следующим образом: для каждого поступающего элемента <tex>a_i</tex> вычислим его хэш <tex>h(a_i)</tex> и представим его в двоичном виде. Тогда первые <tex>r</tex> бит этого двоичного представления будут характеризовать номер корзины <tex>j</tex>, а оставшиеся биты сформируют остаточный хэш <tex>h'(a_i)</tex>, который и будет использоваться для поиска максимального количества начальных нулей в корзине <tex>\mathcal{M}_j</tex>.
 +
 
 +
[[Файл:Hll_bins.jpg|512px]]
 +
 
 +
Для каждой корзины вычислим соответствующее <tex>z_j</tex>, равное максимальному количеству ведущих нулей среди элементов этой корзины. Тогда оценкой для числа различных элементов в корзине будет <tex>2^{z_j}</tex>.
 +
 
 +
Логично было бы предположить, что в таком случае итоговым ответом на задачу будет <tex> \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} </tex>, но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок:
 +
 
 +
<tex>result \approx \alpha \cdot (2^r)^2 \cdot I</tex>
 +
 
 +
*<tex>I</tex> {{---}} это индикатор, вычисляемый по формуле <tex>I = (\sum\limits_{j=0}^{2^{r - 1}} \frac{1}{2^{z_j}})^{-1} </tex>
 +
 
 +
*<tex>\alpha</tex> {{---}} корректирующий множитель, вычисляемый по формуле <tex>\alpha = (2^r  \int\limits_{0}^{\infty} (log_2{\frac{2 + u}{1 + u}})^{2^r} \,du )^{-1}</tex>.
 +
 
 +
Поскольку множитель <tex>\alpha</tex> может быть достаточно сложным для вычисления, можно подобрать его примерное значение в зависимости от <tex>r</tex>:
 +
 
 +
:<tex>
 +
\alpha_{r}\approx\begin{cases}
 +
r=4 & 0.673\\
 +
r=5 & 0.697\\
 +
r=6 & 0.709\\
 +
r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}}
 +
\end{cases}
 +
</tex>
 +
 
 +
==Асимптотика==
 +
Оценка времени работы: <tex>\mathcal{O}(n)</tex>, где <tex>n</tex> {{---}} количество элементов в исходном наборе.
 +
 
 +
Оценка дополнительной памяти: <tex>2^r \cdot log_2(k) = 2^r \cdot log_2 log_2 m </tex>, где <tex>m</tex> {{---}} количество возможных значений хэш-функции.
 +
 
 +
 
 +
==Источники информации==
 +
*[[wikipedia:en:HyperLogLog | Wikipedia {{---}} HyperLogLog algorithm]]
 +
*[http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier {{---}} HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm]
 +
 
 +
[[Категория: Продвинутые алгоритмы]]
 +
[[Категория: Поиск количества различных элементов в потоке данных]]
 +
[[Категория: Вероятностные алгоритмы]]

Версия 14:59, 15 января 2022

HyperLogLog — это вероятностный алгоритм, оценивающий количество различных элементов в больших потоках данных. Является стриминговым алгоритмом (англ. streaming algorithm), то есть обрабатывает последовательно поступающие данные в один проход.

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

Точность

При использовании [math]m[/math] единиц дополнительной памяти алгоритм HyperLogLog оценивает количество различных элементов со стандартной ошибкой около [math]\frac{1.04}{\sqrt{m}}[/math], то есть при оценке данных > 109 этому алгоритму потребуется всего 1.5 kB памяти для получения ответа с точностью 2%.

Предыдущий алгоритм LogLog, использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.

Идея алгоритма

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

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

Но при таком подходе могут возникать различные проблемы за счёт большой дисперсии получаемой величины, а также некоторых крайних случаев: к примеру, если хэш некоторого элемента будет равен [math]0[/math], то максимальное количество ведущих нулей сразу станет равным [math]log_2{m}[/math], где [math]m[/math] — максимальное значение выбранной хэш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на [math]2^r[/math] корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.

Описание алгоритма

  • [math]\mathcal{M}[/math] — исходный набор элементов [math]a_1 ... a_n[/math].
  • [math]h : \mathcal{U} \to {0, 1 ... 2^k - 1}[/math] — выбранная хэш-функция с возможными значениями от [math]0[/math] до [math]m - 1[/math], [math]k = log_2{m}[/math].
  • [math]r[/math] — количество бит исходного хэша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.
  • [math]z_j[/math] — максимальное наблюдаемое количество начальных нулей в корзине под номером [math]j[/math].

Разобьём исходный набор [math]\mathcal{M}[/math] на наборы [math]\mathcal{M}_0..\mathcal{M}_{2^r - 1}[/math] следующим образом: для каждого поступающего элемента [math]a_i[/math] вычислим его хэш [math]h(a_i)[/math] и представим его в двоичном виде. Тогда первые [math]r[/math] бит этого двоичного представления будут характеризовать номер корзины [math]j[/math], а оставшиеся биты сформируют остаточный хэш [math]h'(a_i)[/math], который и будет использоваться для поиска максимального количества начальных нулей в корзине [math]\mathcal{M}_j[/math].

Hll bins.jpg

Для каждой корзины вычислим соответствующее [math]z_j[/math], равное максимальному количеству ведущих нулей среди элементов этой корзины. Тогда оценкой для числа различных элементов в корзине будет [math]2^{z_j}[/math].

Логично было бы предположить, что в таком случае итоговым ответом на задачу будет [math] \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} [/math], но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок:

[math]result \approx \alpha \cdot (2^r)^2 \cdot I[/math]

  • [math]I[/math] — это индикатор, вычисляемый по формуле [math]I = (\sum\limits_{j=0}^{2^{r - 1}} \frac{1}{2^{z_j}})^{-1} [/math]
  • [math]\alpha[/math] — корректирующий множитель, вычисляемый по формуле [math]\alpha = (2^r \int\limits_{0}^{\infty} (log_2{\frac{2 + u}{1 + u}})^{2^r} \,du )^{-1}[/math].

Поскольку множитель [math]\alpha[/math] может быть достаточно сложным для вычисления, можно подобрать его примерное значение в зависимости от [math]r[/math]:

[math] \alpha_{r}\approx\begin{cases} r=4 & 0.673\\ r=5 & 0.697\\ r=6 & 0.709\\ r\ge7 & \frac{0.7213}{1+\frac{1.079}{2^r}} \end{cases} [/math]

Асимптотика

Оценка времени работы: [math]\mathcal{O}(n)[/math], где [math]n[/math] — количество элементов в исходном наборе.

Оценка дополнительной памяти: [math]2^r \cdot log_2(k) = 2^r \cdot log_2 log_2 m [/math], где [math]m[/math] — количество возможных значений хэш-функции.


Источники информации