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