Участник:Warmte - История изменений

Warmte в 19:05, 24 января 2022

2022-01-24T19:05:15Z

Warmte в 18:59, 24 января 2022

2022-01-24T18:59:05Z

Warmte в 18:53, 18 января 2022

2022-01-18T18:53:36Z

Внесённые изменения

Warmte в 18:19, 18 января 2022

2022-01-18T18:19:14Z

Warmte в 18:18, 18 января 2022

2022-01-18T18:18:32Z

Warmte в 11:59, 15 января 2022

2022-01-15T11:59:23Z

Warmte: Новая страница: «1.»

2021-12-22T09:21:56Z

Новая страница: «1.»

Новая страница

@@ Строка 66: / Строка 66: @@
 # Оценка величины 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>\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{reg}} + \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> представляют собой осциллирующие функции с маленькой амплитудой, поддающиеся вычислению. Хотя их влияние в теории может быть компенсировано только частично, ими можно безопасно пренебречь для всех практических целей.
@@ Строка 81: / Строка 81: @@
 }}
-Основная задача представляет оценку асимптотической зависимости величин <tex>\mathbb{E}_n</tex> и <tex>\mathbb{D}_n</tex> от индикатора <tex>Z = \frac{1}{2^{-z_j}}</tex>.
+Основная задача представляет оценку асимптотической зависимости величин <tex>\mathbb{E}_n</tex> и <tex>\mathbb{D}_n</tex> от индикатора <tex>Z = \frac{1}{\sum 2^{-z_j}}</tex>.
 Краткий план доказательства имеет следующий вид:

@@ Строка 15: / Строка 15: @@
 }}
-В основе алгоритма '''HyperLogLog''' лежит наблюдение, что мощность набора [[wikipedia:ru:Равномерное_распределение|равномерно распределенных]] случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>.
+В основе алгоритма '''HyperLogLog''' лежит наблюдение, что мощность набора [[wikipedia:ru:Равномерное_распределение|равномерно распределенных]] на заданном интервале <tex>[0, m-1]</tex> случайных чисел можно оценить, вычислив максимальное количество ведущих нулей в двоичном представлении каждого числа в наборе. Таким образом, если максимальное наблюдаемое количество начальных нулей равно <tex>n</tex>, то оценка количества различных элементов в наборе будет <tex>2^n</tex>.
 Суть алгоритма заключается в следующем: к каждому элементу исходного набора применяется [[wikipedia:ru:Хеш-функция|хеш-функция]] для получения набора равномерно распределенных случайных чисел с той же мощностью, что и исходный набор. Затем мощность этого случайно распределенного набора оценивается с помощью описанного выше алгоритма.
-Но при таком подходе могут возникать различные проблемы за счёт большой [[wikipedia:ru:Дисперсия_случайной_величины|дисперсии]] получаемой величины, а также некоторых крайних случаев: к примеру, если хэш некоторого элемента будет равен <tex>0</tex>, то максимальное количество ведущих нулей сразу станет равным <tex>log_2{m}</tex>, где <tex>m</tex> {{---}} максимальное значение выбранной хэш-функции. Чтобы избежать подобных проблем и минимизировать дисперсию, модифицируем алгоритм следующим образом: разделим исходный поток элементов на <tex>2^r</tex> корзин, для каждой из них вычислим максимальное наблюдаемое количество начальных нулей среди элементов в этой корзине, а затем на основе полученных для всех корзин значений вычислим итоговый ответ на задачу.
+Но при таком подходе могут возникать различные проблемы за счёт большой [[wikipedia:ru:Дисперсия_случайной_величины|дисперсии]] получаемой величины, а также некоторых крайних случаев: к примеру, если хеш некоторого элемента будет равен <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>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>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>\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]]
@@ Строка 40: / Строка 40: @@
   <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>\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>:
@@ Строка 76: / Строка 76: @@
 reg=64 & 1.054\\
 reg=126 & 1.046\\
-reg\to\infty & \sqrt{3 log(2) - 1} = 1.03896
+reg\to\infty & \sqrt{3 \log(2) - 1} = 1.03896
 \end{cases}
 </tex>
@@ Строка 95: / Строка 95: @@
 Оценка времени работы: <tex>\mathcal{O}(n)</tex>, где <tex>n</tex> {{---}} количество элементов в исходном наборе.
-Оценка дополнительной памяти: <tex>\mathcal{O}(2^r \cdot log_2 log_2 n) </tex>.
+Оценка дополнительной памяти: <tex>\mathcal{O}(2^r \cdot \log_2 \log_2 n) </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 log(\frac{2^r}{V})</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 \log(\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>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>E</tex> в корректировке не нуждается.

← Предыдущая		Версия 18:19, 18 января 2022
Строка 104:		Строка 104:

	[[Категория: Продвинутые алгоритмы]]		[[Категория: Продвинутые алгоритмы]]
−	~~[[Категория: Поиск количества различных элементов в потоке данных]]~~
	[[Категория: Вероятностные алгоритмы]]		[[Категория: Вероятностные алгоритмы]]

@@ Строка 5: / Строка 5: @@
 ==Точность==
-При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{m}}</tex>, то есть при оценке данных > 10<sup>9</sup> этому алгоритму потребуется всего 1.5 kB памяти для получения ответа с точностью 2%.
+При использовании <tex>m</tex> единиц дополнительной памяти алгоритм '''HyperLogLog''' оценивает количество различных элементов со стандартной ошибкой около <tex>\frac{1.04}{\sqrt{2^r}}</tex>. Также этот алгоритм способен оценивать значения, превышающие  10<sup>9</sup>, используя 1.5 kB памяти для получения ответа с точностью 2%.
 Предыдущий алгоритм '''LogLog''', использовавшийся для решения этой задачи, достигал сравнимой точности ответа при использовании 64% от оригинальных объемов памяти.
@@ Строка 17: / Строка 17: @@
 ==Описание алгоритма==
-*<tex>\mathcal{M}</tex> {{---}} исходный набор элементов <tex>a_1 ... a_n</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>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>r</tex> {{---}} количество бит исходного хэша, характеризующих номер корзины, в которую будет отправлен соответствующий элемент.
-*<tex>z_j</tex> {{---}} максимальное наблюдаемое количество начальных нулей в корзине под номером <tex>j</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>.
@@ Строка 33: / Строка 33: @@
 Логично было бы предположить, что в таком случае итоговым ответом на задачу будет <tex> \sum\limits_{j=0}^{2^{r - 1}} 2^{z_j} </tex>, но такой подход приводит не к самому выгодному результату. Выгоднее всего будет пересчитывать результат при помощи среднего гармонического всех полученных оценок:
-<tex>result \approx \alpha \cdot (2^r)^2 \cdot I</tex>
+<tex>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>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>\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>:
@@ Строка 49: / Строка 49: @@
 \end{cases}
 </tex>
 ==Асимптотика==
@@ Строка 55: / Строка 93: @@
 Оценка дополнительной памяти: <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]

← Предыдущая		Версия 11:59, 15 января 2022
Строка 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]
		+
		+	[[Категория: Продвинутые алгоритмы]]
		+	[[Категория: Поиск количества различных элементов в потоке данных]]
		+	[[Категория: Вероятностные алгоритмы]]