The szl language (which was used at Google for log processing) has a output type called unique(n) [1], which uses a simple algorithm: it stores the smallest n s

The szl language (which was used at Google for log processing) has a output type called unique(n) [1], which uses a simple algorithm: it stores the smallest n sorted MD5 hashes, assumes that the hash is uniformly distributed and there are no collisions, and estimates that total unique count as highest possible hash * n / highest stored hash. Edit: fixed the formula. [1]: http://code.google.com/p/szl/source/browse/trunk/src/emitters/szlunique.cc http://code.google.com/p/szl/source/browse/trunk/src/emitter...