Изменения

Перейти к: навигация, поиск

Участник:Warmte

6002 байта добавлено, 21:18, 18 января 2022
Нет описания правки
==Точность==
При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{m2^r}}</tex>. Также этот алгоритм способен оценивать значения, то есть при оценке данных > превышающие 10<sup>9</sup> этому алгоритму потребуется всего , используя 1.5 kB памяти для получения ответа с точностью 2%.
Предыдущий алгоритм '''LogLog''', использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.
==Описание алгоритма==
*<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>.
Логично было бы предположить, что в таком случае итоговым ответом на задачу будет <tex> \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} </tex>, но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок:
<tex>result E \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>:
\end{cases}
</tex>
 
==Доказательство==
{{Определение
|definition=
'''Идеальным мультимножеством''' с количеством различных элементов <tex>n</tex> называется последовательность, полученная произвольными повторениями и перестановками, применяемыми к <tex>n</tex> равномерно распределенным случайным величинам на действительном интервале [0, 1].
}}
 
{{Теорема
|statement=
Пусть алгоритм '''HyperLogLog''' применяется к идеальному мультимножеству, содержащему <tex>n</tex> различных элементов (число <tex>n</tex> нам неизвестно), используя <tex>reg = 2^r</tex> корзин, и пусть <tex>E</tex> {{---}} полученная результирующая оценка количества различных элементов в этом мультимножестве.
 
# Оценка величины E в таком случае асимптотически почти несмещенная, а именно: <br /> <tex> \frac{1}{n} \mathbb{E}(E) \overset{n \to \infty}{=} 1 + \delta_1(n) + o(1)</tex>, где <tex>|\delta_1(n)| < 5 \cdot 10^{-5}</tex> при <tex>reg \geq 16</tex>
 
# Стандартная ошибка, равная <tex>\frac{1}{n}\sqrt{\mathbb{D}_n(E)}</tex>, вычисляется следующим образом: <br /> <tex>\frac{1}{n}\sqrt{\mathbb{D}_n(E)} \overset{n \to \infty}{=} \frac{\beta_{reg}}{\sqrt{r}} + \delta_2(n) + o(1)</tex>, где <tex>|\delta_2(n)| < 5 \cdot 10^{-4}</tex> при <tex>reg \geq 16</tex>
 
<tex>\delta_1(n)</tex>, <tex>\delta_2(n)</tex> представляют собой осциллирующие функции с маленькой амплитудой, поддающиеся вычислению. Хотя их влияние в теории может быть компенсировано только частично, ими можно безопасно пренебречь для всех практических целей.
Константа <tex>\beta_{reg}</tex>, в свою очередь, вычисляется следующим образом:
:<tex>
\beta_{reg}=\begin{cases}
reg=16 & 1.106\\
reg=32 & 1.070\\
reg=64 & 1.054\\
reg=126 & 1.046\\
reg\to\infty & \sqrt{3 log(2) - 1} = 1.03896
\end{cases}
</tex>
}}
 
Основная задача представляет оценку асимптотической зависимости величин <tex>\mathbb{E}_n</tex> и <tex>\mathbb{D}_n</tex> от индикатора <tex>Z = \frac{1}{2^{-z_j}}</tex>.
 
Краткий план доказательства имеет следующий вид:
 
# Сначала выводятся значение величины <tex>\alpha_r</tex>, которая и делает оценку <tex>E</tex> асимптотически почти несмещенной, и величина стандартной ошибки.
# Затем производится непосредственная оценка величин <tex>\mathbb{E}_n(Z)</tex> и <tex>\mathbb{D}_n(Z)</tex>.
# Поскольку значение <tex>\mathbb{E}_n(Z)</tex> достаточно сложно вычислить, сначала исследуется величина <tex>\mathbb{E}_{\mathcal{P}(\lambda)}(Z)</tex>, то есть ситуация, когда ожидаемое значение величины <tex>Z</tex> не фиксировано, а удовлетворяет закону Пуассона с некоторым параметром <tex>\lambda</tex>.
# После этого остаётся доказать, что при <tex>\lambda := n</tex> поведение <tex>\mathbb{E}_n(Z)</tex> и <tex>\mathbb{E}_{\mathcal{P}(\lambda)}(Z)</tex> асимптотически близко.
 
С полным доказательством этой теоремы можно ознакомиться в [http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf оригинальной статье].
==Асимптотика==
Оценка дополнительной памяти: <tex>2^r \cdot log_2(k) = 2^r \cdot log_2 log_2 m </tex>, где <tex>m</tex> {{---}} количество возможных значений хэш-функции.
==Практические оптимизации==
Полученное при помощи алгоритма HyperLogLog значение <tex>E</tex> может оказаться неточным и нуждается в корректировке:
* При <tex>E \leq \frac{5}{2}2^r</tex> в оценке могут появляться нелинейные искажения, которые необходимо скорректировать. Вычислим количество <tex>z_j</tex> равных <tex>0</tex>, обозначим эту величину за <tex>V</tex>. Если <tex>V = 0</tex>, то уже полученное алгоритмом значение <tex>E</tex> в корректировке не нуждается, иначе оно должно быть вычислено по формуле <tex>E_{result} = 2^r \frac{2^r}{V}</tex>.
* В том случае, если значение <tex>E</tex> превосходит ограничение на размер <tex>z_j</tex>, итоговая оценка также должна быть скорректирована. Рассмотрим 32-битный случай: при <tex>E > \frac{2^{32}}{30}</tex> итоговое значение можно вычислить как <tex>E_{result} = -2^{32} log(1 - \frac{E}{2^{32}})</tex>. Это может быть полезным при больших <tex>n</tex>, близких к (в нашем примере) 2^{32}, когда вероятность коллизии при хешировании становится довольно высокой.
* В остальных случаях итоговая оценка <tex>E</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]
8
правок

Навигация