1
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 4 '21 at 3:53
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Dec 4 '21 at 10:50
  • $\begingroup$ (@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?) $\endgroup$
    – greybeard
    Dec 4 '21 at 10:53
  • $\begingroup$ Excellent question. Welcome to the site. $\endgroup$
    – 6005
    Dec 9 '21 at 0:22
2
$\begingroup$

Great question! First, I do not know how YouTube's view counting works, but I will answer the question you ask about counting unique visitors.

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.

However, there are much better solutions known which are approximation algorithms to the true value, such as HyperLogLog. The idea of these solutions the following algorithm, which is straightforward to understand, and quite beautiful:

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

But there are improvements to make it even more accurate, and these are incorporated in algorithms such as HyperLogLog.

$\endgroup$

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.