How to efficiently see if a value is in a set

I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every unique view it receives (let's imagine it does if it doesn't already). There are millions or billions of viewers per video. That means to see if it a person first time seeing a video is O(1) (hash set). However, that means the set size has to be possibly millions or billions in length per video (there are a lot of videos), that's a lot of space. How can you get the same result, adding to a set of unique users without possibly using all that space? Is there a more space-efficient solution possible?

• A billion entries in a red-black tree will amount to a height of approximately 29. 29 comparisons for a billion values is a pretty reasonable amount, wouldn't you agree? A trillion entries will generate a tree with 39 levels. Dec 4 '21 at 3:53
• There on the order of $10^{10}$ humans $h$. There is a lot of videos $v$. Depending on context, there may be a better solution to first occurrence of $(h, v)$ than to keep that for each video independently. Dec 4 '21 at 10:50
• (@davidbuzatto: Is that (29 for $10^9$) close to the lower limit, the upper limit or the expected value? For expected value, which is more useful: tree height or average depth of leaf?) Dec 4 '21 at 10:53
• Excellent question. Welcome to the site.
– 6005
Dec 9 '21 at 0:22

This problem is known as the Count-distinct problem. If you want to really count the exact number of unique values, then in the worst case, it can only be done if you save the entire set of values seen so far; this requires at least $$\Omega(N)$$ space to store whether or not you have seen $$N$$ different values, so it becomes infeasible if $$N$$ is large.
• For each input value, calculate $$\mathsf{hash}(v)$$, where $$\mathsf{hash}$$ is a hash function. Look at how many $$0$$s are at the end of $$\mathsf{hash}(v)$$ (trailing zeros), and keep track of the maximum number of trailing zeros seen so far, $$k$$. Then estimate the number of distinct elements as $$2^k$$.
It turns out that the estimate $$2^k$$ is a good approximation to the real number of unique views, and it only requires storing $$k$$, which takes very little space.