I'm going to adapt the Hyperloglog algorithm to count distinct numbers from a stream. But now, it is more challenging; say, there is a condition: the number needs to exist in the database so that it will be considered. If it does not exist in the database, then we don't put that number in the list of distinct numbers.

Assuming that each time of query we can only query one number to know if it exists or not.

The goal here is to find the number of distinct values which exist in the database with as least queries as possible. Any modification of Hyperloglog so that we can use it in such case?

I am thinking of using reservoir sampling to keep a smaller distribution of the database so that we will know the existence percentage of the number in the stream. Then multiply with the result of Hyperloglog to estimate that. Does that make sense?



Your Answer

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