3 ms·
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.o
by BenoitP 11y ago
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 https://en.wikipedia.org/wiki/HyperLogLog
- sammoth 11y agoWhat part of the algorithm would cause the number to change significantly every time you run the query?
- BenoitP 11y agoAll 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/af045cb4199959c07fb4422e605573e180491191/src/main/java/com/clearspring/analytics/stream/cardinality/RegisterSet.java#L87 https://github.com/addthis/stream-lib/blob/af045cb4199959c07... [2] https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java https://github.com/addthis/stream-lib/blob/master/src/main/j...