Flajolet's HyperLogLog appears to kick the butt of my home-grown equivalent, and it's in redis now: http://antirez.com/news/75 @antirez