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.