Гиперлоглог

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

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

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

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

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

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

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

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

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

Данные HyperLogLog хранятся в массиве $M$ из $m$ счетчиков (или «регистров»), которые инициализируются значением 0. Массив $M$ , инициализированный из мультинабора $S,$ называется эскизом HyperLogLog S.

Добавить [ править ]

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

{\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}$ из графа:

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

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

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

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

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

соображения Практические

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

\alpha _{m}\approx {\begin{cases}0.673,&{\text{for }}m=16;\\0.697,&{\text{for }}m=32;\\0.709,&{\text{for }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{for }}m\geq 128.\end{cases}}

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

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

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

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}$

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

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

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

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

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

ХЛЛ++ [ править ]

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

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

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

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

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

Дальнейшее чтение [ править ]

«Новые алгоритмы оценки мощности для эскизов HyperLogLog» (PDF) . Проверено 29 октября 2016 г.

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

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Флажоле, Филипп; Фьюзи, Эрик; Гандуэ, Оливье; Менье, Фредерик (2007). «Гиперлоглог: анализ почти оптимального алгоритма оценки мощности» (PDF) . Труды дискретной математики и теоретической информатики . АХ . Нанси, Франция : 137–156. CiteSeerX 10.1.1.76.4286 . Проверено 11 декабря 2016 г.
^ Дюран, М.; Флажоле, П. (2003). «LogLog подсчет больших мощностей». (PDF) . В Г. Ди Баттиста и У. Цвик (ред.). Конспекты лекций по информатике . Ежегодный европейский симпозиум по алгоритмам (ESA03). Том. 2832. Спрингер. стр. 605–617.
^ Флажоле, Филипп; Мартин, Дж. Найджел (1985). «Алгоритмы вероятностного подсчета для приложений баз данных» (PDF) . Журнал компьютерных и системных наук . 31 (2): 182–209. дои : 10.1016/0022-0000(85)90041-8 .
^ С. Хойле; М. Нункессер; Зал (2013). «HyperLogLog на практике: алгоритмическая разработка современного алгоритма оценки мощности» (PDF) . сек 4.
^ Ванг, Кю-Янг; Вандер-Занден, Брэд Т; Тейлор, Ховард М. (1990). «Алгоритм вероятностного подсчета с линейным временем для приложений баз данных» . Транзакции ACM в системах баз данных . 15 (2): 208–229. дои : 10.1145/78922.78925 . S2CID 2939101 .
^ Jump up to: Перейти обратно: ^а ^б «HyperLogLog на практике: алгоритмическая разработка современного алгоритма оценки мощности» . Проверено 19 апреля 2014 г.
^ «PFCOUNT – Redis» .
^ Коэн, Э. (март 2015 г.). «Пересмотр эскизов на всех расстояниях: оценки HIP для анализа массивных графиков». Транзакции IEEE по знаниям и инженерии данных . 27 (9): 2320–2334. arXiv : 1306.3284 . дои : 10.1109/TKDE.2015.2411606 .
^ Тинг, Д. (август 2014 г.). «Потоковый приблизительный подсчет отдельных элементов» . Материалы 20-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 442–451. дои : 10.1145/2623330.2623669 . ISBN 978-1-4503-2956-9 . S2CID 13179875 .
^ Сяо, К.; Чжоу, Ю.; Чен, С. (май 2017 г.). «Лучше с меньшим количеством битов: повышение производительности оценки мощности больших потоков данных». IEEE INFOCOM 2017 — Конференция IEEE по компьютерным коммуникациям . стр. 1–9. дои : 10.1109/INFOCOM.2017.8057088 . ISBN 978-1-5090-5336-0 . S2CID 27159273 .

[flajolet07-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Флажоле, Филипп; Фьюзи, Эрик; Гандуэ, Оливье; Менье, Фредерик (2007). «Гиперлоглог: анализ почти оптимального алгоритма оценки мощности» (PDF) . Труды дискретной математики и теоретической информатики . АХ . Нанси, Франция : 137–156. CiteSeerX 10.1.1.76.4286 . Проверено 11 декабря 2016 г.

[2] Дюран, М.; Флажоле, П. (2003). «LogLog подсчет больших мощностей». (PDF) . В Г. Ди Баттиста и У. Цвик (ред.). Конспекты лекций по информатике . Ежегодный европейский симпозиум по алгоритмам (ESA03). Том. 2832. Спрингер. стр. 605–617.

[3] Флажоле, Филипп; Мартин, Дж. Найджел (1985). «Алгоритмы вероятностного подсчета для приложений баз данных» (PDF) . Журнал компьютерных и системных наук . 31 (2): 182–209. дои : 10.1016/0022-0000(85)90041-8 .

[4] С. Хойле; М. Нункессер; Зал (2013). «HyperLogLog на практике: алгоритмическая разработка современного алгоритма оценки мощности» (PDF) . сек 4.

[5] Ванг, Кю-Янг; Вандер-Занден, Брэд Т; Тейлор, Ховард М. (1990). «Алгоритм вероятностного подсчета с линейным временем для приложений баз данных» . Транзакции ACM в системах баз данных . 15 (2): 208–229. дои : 10.1145/78922.78925 . S2CID 2939101 .

[Heule13-6] Jump up to: Перейти обратно: ^а ^б «HyperLogLog на практике: алгоритмическая разработка современного алгоритма оценки мощности» . Проверено 19 апреля 2014 г.

[7] «PFCOUNT – Redis» .

[8] Коэн, Э. (март 2015 г.). «Пересмотр эскизов на всех расстояниях: оценки HIP для анализа массивных графиков». Транзакции IEEE по знаниям и инженерии данных . 27 (9): 2320–2334. arXiv : 1306.3284 . дои : 10.1109/TKDE.2015.2411606 .

[9] Тинг, Д. (август 2014 г.). «Потоковый приблизительный подсчет отдельных элементов» . Материалы 20-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 442–451. дои : 10.1145/2623330.2623669 . ISBN 978-1-4503-2956-9 . S2CID 13179875 .

[10] Сяо, К.; Чжоу, Ю.; Чен, С. (май 2017 г.). «Лучше с меньшим количеством битов: повышение производительности оценки мощности больших потоков данных». IEEE INFOCOM 2017 — Конференция IEEE по компьютерным коммуникациям . стр. 1–9. дои : 10.1109/INFOCOM.2017.8057088 . ISBN 978-1-5090-5336-0 . S2CID 27159273 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]