HyperLogLog
Перейти к навигации
Перейти к поиску
Шаблон:Дописать HyperLogLog — вероятностный алгоритм для приблизительного подсчета уникальных элементов в мультимножестве. Вычисление точной мощности множества требует памяти пропорциональной самой мощности, что зачастую неприемлемо при работе с большими объёмами данных. Вероятностные алгоритмы вычисления мощности, такие как HyperLogLog, требуют значительно меньших объёмов памяти, вычисляя приближенное значение мощностиШаблон:Нет АИ. Алгоритм HyperLogLog способен вычислить приближенное значение мощности порядка с погрешностью в 2 %, используя 1,5 килобайт памяти.
HyperLogLog — модификация алгоритма LogLog, основанного на идеях алгоритма Флажоле — Мартина. HyperLogLog опубликован в 2007 году Ф. Флажоле и соавторами.[1]
Примечания
- ↑ P. Flajolet, E. Fusy, O. Gandouet, F. Meunier - HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm. Шаблон:Comment Proc AH: 137–156, 2007