4 ms·
Surprised nobody's mentioned Hyper Log Log (or its more recent variants). A probabilistic constant-space unique cardinality estimator (i.e. if I see a billion e
by venantius 8y ago
Surprised nobody's mentioned Hyper Log Log (or its more recent variants). A probabilistic constant-space unique cardinality estimator (i.e. if I see a billion events, how many are unique?) that also supports set operations.
- dswalter 8y agoThe underlying reasoning behind PCSA/HLL (that if you squint, you can use the zeros and ones from a hash as analogues to coin-flipping, and can use the probability of the rarest event seen to estimate the total number of events seen) is excellent. Count-min-sketch is also beautifully simple.