How should I estimate the number of unique elements in a randomly shuffled list? I'm in a situation when the memory I have is much smaller than memory needed to store all unique elements. Something efficient with confidence interval and/or a reference for such procedure would be great
Asked
Active
Viewed 168 times
1 Answers
3
Fellow CVer @rrenaud cited this paper as a key reference for number of unique value estimation. He suggested also to check out the Good Turing frequency estimator, which was developed to estimate the proportion of elements that occur n times, including the case where n = 1 (i.e., unique values).
Here is a link to @rrenaud's answer to the similar question.
Have fun!
Brash Equilibrium
- 3,845
-
I agree with the direction suggested. Here is another very good review: http://www.jstor.org/stable/2290733 – JohnRos Nov 30 '11 at 10:43
-
It would be good to point to the original question/answer that cited the evidence by rrenaud. I assume you are referring to the answer on this question, How can I estimate unique occurrence counts from a random sampling of data? – Andy W Nov 30 '11 at 13:33
-
@Andy W that's the one! – Brash Equilibrium Nov 30 '11 at 14:32
-
@Andy W: I added a reference to the original answer. Thanks for the stats.exchangeiquette pro-tip. I will observe it in the future! – Brash Equilibrium Dec 01 '11 at 00:28