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

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

Фильтр минимального количества и Блума имеет свой собственный набор ограничений, но Google не помогает предоставить много информации о приложениях и ограничениях Hyperloglog.

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


redis cardinality hyperloglog
person blueskin    schedule 05.04.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

person otmar    schedule 06.04.2016