Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading this algorithm in these notes for counting the number of distinct items in a stream.

From my understanding, the basic idea is that if such number is big enough, the distance between the numbers generated by the hash function will be, on average, the same and equal to $1/(k+1)$, where $k$ is the number of distinct element. Hence, one can derive $k$ from that. However, I don't follow the reasoning in slide 6. Why would $2^R$ be "around" $m$?

share|cite|improve this question
up vote 1 down vote accepted

In words, I'd say the two preceding lines in the slide say "for a value $v$ much larger than $m$, it is very unlikely that $2^R$ will exceed $v$" respectively "for a value $v$ much smaller than $m$, it is very likely that $2^R$ will exceed $v$" (take $v=2^r$ both times). It does not seem an enormous strecth to conclude that most of the time $2^R$ will not be much larger than $m$ (first clause) but not much smaller than $m$ either (second clause), in other words, fairly close to $m$.

share|cite|improve this answer
what if one recorded the minimum value seen so far? if the number of distinct items is sufficiently large, the distance between different elements (after hashing) will be uniform. hence, the length of the interval (all ones word) divided by the minimum should provide an estimate of the number of different items. does that make sense? – ACAC Sep 25 '12 at 3:00
The authors, in the PCSA paper, mention in passing in the Conclusion section: "the binary logarithm of the minimal hashed value encountered (hashed values being considered are real [O; 11 numbers) provides an approximation to log, lln, but the resulting algorithm appears to be slightly less accurate than PCSA". Cannot copy correctly from PDF, sorry about formatting. Sounds like they already knew about what you're onto, as is usual with the elders. – bruce.banner Mar 25 at 14:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.