Ограничения Redis Hyperloglog

Question

Я пытаюсь решить проблему хакерским способом с помощью Redis Hyperloglog, но я пытаюсь понять, что это ограничения и допущения Hyperloglog по данным или распределению.

Фильтр count-min и bloom имеет свой собственный набор ограничений, но google не помогает в предоставлении подробной информации о приложениях и ограничениях Hyperloglog.

Я использую Redis Hyperloglog и как Antirez описывает there are no practical limits to the cardinality of the sets we can count. Но с точки зрения теории, делает ли Hyperloglog какие-либо предположения/ограничения относительно данных или распределения?

Answer 1

Алгоритм HyperLogLog предполагает, что используется сильная универсальная хеш-функция. Redis использует MurmurHash64A, который должен быть достаточно хорош с практической точки зрения. Реализация Redis HyperLogLog использует 6 бит на регистры, что позволяет представлять любые длины бит в 64-битных хеш-значениях. Следовательно, единственное ограничение, которое я вижу, - это 64-битное хеш-значение. Если мощность порядка 2^64, будет много хеш-коллизий, что в конечном итоге приведет к большим ошибкам оценки. Однако мощности этого порядка величины никогда не происходят на практике.