Algebird HyperLogLog — индекс регистра и биты значения регистра

Я новичок в HyperLogLog и Scala и пытаюсь использовать реализацию HyperLogLog Twitter Algebird — https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/HyperLogLog.scala.

В других реализациях HyperLogLog (например, для Postgres https://github.com/aggregateknowledge/postgresql-hll) Я могу настроить алгоритм с количеством сегментов (используя log2m), а также с шириной регистров, исходя из моих ожидаемых требований к полноте и точности.

У меня возникли проблемы с пониманием того, как эти значения используются/вычисляются в реализации Algebird. В частности, я использую класс HyperLogLogMonoid.


postgresql twitter scala monoids abstract-algebra
person DJElbow    schedule 22.09.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Единственным параметром алгоритма HyperLogLog является количество сегментов m, где m = 2 ^ b. HyperLogLogMonoid параметризуется параметром val bits: Int, который эквивалентен параметру b в оригинальной статье.

person kosii    schedule 22.09.2015
comment
Я понимаю эту часть. Но в других частях кода я вижу вычисления для reducedBits The new number of bits to use и jLen, которые, похоже, корректируют фактическое количество битов, используемых для m. Но, как я уже упоминал, я новичок в алгоритме и Scala, и у меня проблемы с пониманием кода. - person DJElbow; 23.09.2015
comment
reducedBits используется в методе downsize. Этот метод используется для возврата нового экземпляра HLL с уменьшенным количеством битов, используемых для представления вашей структуры HyperLogLog, таким образом уменьшая память, используемую для ваших вычислений, и увеличивая стандартную ошибку. - person kosii; 23.09.2015
comment
Да, я вижу это. На самом деле я пытаюсь понять, когда на самом деле вычисляются и используются эти уменьшенные биты. - person DJElbow; 23.09.2015
comment
насколько я вижу, он ниоткуда не используется, это просто служебная функция для безопасного изменения размера структуры HLL - person kosii; 23.09.2015