The Flajolet-Martin paper on counting unique items in an infinite stream with constant space [1]: a great, well-written introduction to streaming algorithms that triggered my first "aha" moment in the field. You never forget your first.

[1] http://algo.inria.fr/flajolet/Publications/FlMa85.pdf