2
$\begingroup$

In this blog the author states that the following

So we now have a rather poor estimate of the number of values in the dataset based on bit patterns. How can we improve on it? One straightforward idea is to use multiple independent hash functions. If each hash produces its own set of random outputs, we can record the longest observed sequence of leading 0s from each; at the end we can average our values for a more accurate estimate.

can be replace with

A better approach is one known as stochastic averaging. Instead of using multiple hash functions, we use just a single hash function, but use part of its output to split values into one of many buckets. Supposing we want 1024 values, we can take the first 10 bits of the hash function as a bucket number, and use the remainder of the hash to count leading 0s

I am confused on his description of replacement, can someone help me understand what does take the "first 10 bits of the hash function as a bucket number" mean? And how is it a direct replacement of the hashing multiple times and take the average.

Thanks

Edit:

The author claims that given a random hashed set of element, by counting the highest consecutive k prefix bit that is 0, you can estimate the cardinality of the distinct set to be 2^k.

But using 2^k once might not be a good idea, so he suggest using multiple hashing to determine the average of 2^k. For example given n distinct n hash function. 2^k_approximate = (2^k_1 + 2^k_2 + .....2^k_n)/n

However he claims that multiple hash can be be replace by using the first 10 bit of a single hash function as a bucket number. Which I don't quite understand why that would be similar to the original multi hash average technique.

$\endgroup$
  • 1
    $\begingroup$ There is some context missing here. We don't have to read the blog post (which could disappear) to understand the question. What are we trying to estimate, and how are we doing it? $\endgroup$ – Yuval Filmus Sep 12 '17 at 7:32
1
$\begingroup$

Let us start with the original approach. We compute the hash values of all input elements, and choose the minimal one $h$. If the leading bit is at position $k$, then we estimate that the number of distinct inputs in the output is roughly $2^k$.

The idea behind this is that we think of the minimal hash as a minimum of $N$ random strings, where $N$ is the number of distinct inputs. We expect the leading bit of such a minimum to be at position roughly $\log_2 N$.

When using $D$ different hash functions, the corresponding experiment is

Choose $N$ random strings for each of $D$ many bins.

We then calculate the leading bit of the minimal string in each bin, and use this to estimate $N$.

Now suppose that we use the top $B$ bits to choose one of $2^B$ buckets, and compute the minimum value in each bucket. As before, this should be similar to the following experiment:

Distribute $N$ random strings into $2^B$ bins at random.

As before, we then calculate leading bits and use them to estimate $N$, but since this step is identical to the corresponding step in the multiple hash method, we just concentrate on the first part of the experiment (putting random strings into bins).

We expect each bin to get roughly $N/2^B$ random strings, and so this experiment is very similar to the following one:

Distribute $N/2^B$ random strings for each of $2^B$ many bins.

This is the same as the experiment for multiple hash functions, with $D = 2^B$ and $N$ reduced by a factor of $2^B$.

You might be put off by the difference in $N$. However, this difference disappears when we calculate the number of hash function evaluations. If we have a quota of $M$ hash function evaluations, then in the multiple hash case we can only use $M/D$ inputs, whereas in stochastic averaging we can use $M$ inputs.

$\endgroup$
  • $\begingroup$ Sorry, I am not really following the derivations. So here is my understanding of what the author is trying to do for $D$ hashes. The author apply hash_1 to all elements and find the minimum k_1 (longest leading 0 bit) and record that he continues to find all $k$s (k_1, k_2...k_d), and he average those k and approximate the distinct element to be $2^{k_{avg}}$ , but that is different than Choose N random strings for each of D many bins. since each hash do not get $N/D$ elements but rather all $N$ elements. Am I missing something? $\endgroup$ – Jal Sep 12 '17 at 18:23
  • $\begingroup$ What the author does is (1) distribute $N$ random strings into each of $D$ bins; (2) calculate the minimal string in each bin; (3) approximate $N$ using the minimal strings. My claim is that step 1 already looks very similar when using multiple hash functions and when using stochastic averaging. $\endgroup$ – Yuval Filmus Sep 12 '17 at 18:33

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.