A very similar question was asked at https://cstheory.stackexchange.com/questions/16582/l-0-estimation-not-in-a-stream where links to two particularly useful looking papers were given.  Those were http://dl.acm.org/citation.cfm?id=335230 where you get worst case upper and lower bounds and http://theory.stanford.edu/~sergei/papers/distinct-analco.pdf where you get a good method if the input data has a power law distribution.