A Charming Algorithm for Count-Distinct(justinjaffray.com)

9 pointsby foldUvor 4 Jahren2 comments

https://justinjaffray.com/a-charming-algorithm-for-count-distinct/

1 comments

> I actually had no idea it was possible to do efficient count-distinct without hashes, but it turns out it is!

Since the final algorithm maintains a Set, doesn't it still perform hashes?

foldUvor 4 Jahren

This implementation incidentally uses a hash table, but any set-like data structure would work. This is different from things like HyperLogLog that actually depend on the hash values themselves in order to work.