HyperLogLog

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