8
правок
Изменения
Нет описания правки
'''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] [[Категория: Продвинутые алгоритмы]][[Категория: Поиск количества различных элементов в потоке данных]][[Категория: Вероятностные алгоритмы]]
