Hacker News Reader

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

View on HN

What part of the algorithm would cause the number to change significantly every time you run the query?

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...

Reply on news.ycombinator.com