News for hackers. Stuff that matters.

A comment on This should never happen. Parent comment

Re:This should never happen by BenoitP on Thursday March 31, 2016 @08:00AM (#11396480)
HyperLogLog[1] will do that. You can find it in Redis, Lucene; and I suspect it is also hidden behind BigQuery's count(distinct X)s.

[1] https://en.wikipedia.org/wiki/HyperLogLog

[ Parent | on HN ]
Re:This should never happen by sammoth on Thursday March 31, 2016 @09:56AM (#11397161)
What part of the algorithm would cause the number to change significantly every time you run the query?
[ Parent | on HN ]
Re:This should never happen by BenoitP on Thursday March 31, 2016 @10:19AM (#11397322)
All shards compute their own, and send the result in a non deterministic order. My explanation is that the merge part of HLL depends on the order.

Line 95 of this method [1] from this implementation [2] shows a max(mask(x), mask(y)), which is not associative but is a close proxy to max()(which is associative).

[1] https://github.com/addthis/stream-lib/blob/af045cb4199959c07...

[2] https://github.com/addthis/stream-lib/blob/master/src/main/j...

[ Parent | on HN ]