0
$\begingroup$

Need to understand "intuition" part. It does not make sense to me why $log(d)$ is a good approximation.

We have a stream $\sigma = \{a_1, ..., a_n\}$, with each $n \in [n]$, and this implicitly defines a frequency vector $F = {f_1, ..., f_n}$. Let $d = |\{j : f_j > 0$}| be the number of distinct elements that appear in $\sigma$.

For an integer $p > 0$, let $zeros(p)$ denote the number of zeros that the binary representation of $p$ ends with. Formally,

$zeros(p) = max\{i : 2^{i}$ divides $p\}$

Algorithm:

Initialize:

  1. Choose a random hash function $h$: $[n] \mapsto [n]$ from a 2-universal family;

  2. z $\leftarrow $ 0;

Process $j$: 3. if $zeros(h(j)) > z$ then $z \leftarrow zeros(h(j))$

Output: $2^{z+\frac{1}{2}}$

The basic intuition here is that we expect $1$ out of $d$ distinct tokens to hit $zeros(h(j)) \geq log(d)$, and we don't expect any tokens to hit $zeros(h(j)) >> log(d)$. Thus the max value of $zeros(h(j))$ over the stream - which is what we maintain in $z$ - should give us a good approximation to $log(d)$.

$\endgroup$
  • 1
    $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Mar 8 '16 at 14:15
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 8 '16 at 14:15
  • $\begingroup$ 1. Please attribute your sources. You give a very long quotation. Is that a quote from some source? If so, where? Copying without attribution amounts to plagiarism, which isn't cool. 2. What is your question? I don't see any question here, merely a list of declarative statements. Can you articulate a specific, answerable question? $\endgroup$ – D.W. Mar 9 '16 at 4:58
2
$\begingroup$

The idea is that the hash function $h$ maps elements to random elements. Now think about the likelihood that the last $k$ digits of a random number are $0$. There's a 50/50 chance that the number ends with $0$, but it becomes more and more unlikely as you increase the number of zeroes at the end. For $000$, the probability is already down to $\frac{1}{8}$, and for ten zeroes it's around one in one thousand. So it's very unlikely that any one random number has a lot of zeroes at the end.

So what's the maximum number of zeroes can you expect when you take $d$ random numbers? It's unlikely that one of the $d$ numbers ends in loads of zeroes, but the probabilities are so that it's likely that at least one has $\log{d}$ zeroes.

If you do this with one hash function, that's a pretty rough estimator, but due to the so-called median trick you can do it a couple of times with different hash functions, use the median of the outputs, and the certainty of the result increases exponentially in the number of different hash functions (they have to be independent).

$\endgroup$
  • $\begingroup$ Additionally, as described in "The space complexity of approximating the frequency moments" (Alon, Matias, Szegedy, 2002), a linear hash function (calculations in the field modulo the next power of two strictly greater than n, choose two elements a, b randomly, use h(x) = a•x + b as hash function) suffices. $\endgroup$ – Lorenz Mar 18 '16 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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