I also like the moral predecessor of this algorithm (Morris counting algo I think it's called) which solves the simpler problem of estimating the number of elements in a stream with loglog space. Curiously it appears as an exercise in CLRS.