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.
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 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.