HyperLogLog

HyperLogLog — вероятностный алгоритм для приблизительного подсчета уникальных элементов в мультимножестве. Вычисление точной мощности множества требует памяти пропорциональной самой мощности, что зачастую неприемлемо при работе с большими объёмами данных. Вероятностные алгоритмы вычисления мощности, такие как HyperLogLog, требуют значительно меньших объёмов памяти, вычисляя приближенное значение мощности. Алгоритм HyperLogLog способен вычислить приближенное значение мощности порядка $10^{9}$ с погрешностью в 2 %, используя 1,5 килобайт памяти.

HyperLogLog — модификация алгоритма LogLog, основанного на идеях алгоритма Флажоле — Мартина. HyperLogLog опубликован в 2007 году Ф. Флажоле и соавторами.