4 ms·

Does YouTube generate video URLs completely randomly though? I'd be surprised if that was actually the case.

by paxys 3y ago

timeagain 3y ago
Randomly, probably not. But I bet that they go pretty uniformly through their URL hashing space.
Dylan16807 3y ago
Anything random-ish will make this estimation method work. On either youtube's side or the measuring side. Why would they not be random? Nobody has ever found a pattern that I'm aware of, and there are pretty solid claims of past PRNG use. And a leak of the PRNG seed was likely why they mass-privated all unlisted videos a couple years ago.
jolyon 3y ago
Wait a second. If the IDs are all allocated in a contiguous block, and the author samples the whole space at random—then the estimate will converge to the correct value. If, on the other hand, the IDs are allocated at random, the estimate will also converge to the correct value. If you believe that there is some structure in YouTube video IDs, that would have no effect on this experiment. It would just reduce the fraction of the total address space that YouTube can use. This is a well-known property of "impure" names, and it means there is a good chance that the IDs have no structure. In other words, the video IDs would be "pure" names.
- treesciencebot 3y ago
  Is 32,000 a good enough number to estimate the entirety of the Youtube’s video space? It felt to little for what they are trying to accomplish (especially when they started doing year by year analysis)
  - Dylan16807 3y ago
    When you're estimating a ratio between two outcomes, the rule of thumb is that you want at least 10-100 samples of each outcome, depending on how much precision you want. They got 10,000 samples of hits, and a huge number of samples of misses. Their result should be very accurate. (32,000 was a different number)
  - cbolton 3y ago
    32000 is just the "cheat factor" by which they increase the method's efficiency. I'm not sure how much the "cheating" would affect the precision of the result. But assuming it has no effect, it's easy to estimate this precision: They found X = 24964 videos in a search space of size S = 2^64. For the number of existing videos they report the estimate N = 13,325,821,970. From this we can find their estimate for the probability that a particular ID links to a video: p = N / S ≈ 7.22e-10. So the equivalent number of IDs that they have checked (the number of checks without cheating that would give the same information) is n = X / p ≈ 3.46e13. Since X is a Binomial, its variance is Var(X)=n⋅P(1-P) (where P is the real proportion corresponding to the estimate p above). And N = X⋅S/n so its variance is Var(X)⋅S^2/n^2. The standard deviation of N is thus σ = S⋅sqrt(P⋅(1-P)/n). Now we don't know P but we can use our estimate p instead to find an estimate of σ! We find that the standard deviation of their estimator for the number of YouTube videos is approximately S⋅sqrt(p⋅(1-p)/n) ≈ 8.43e7. That's just 0.633% of N so their estimate is quite precise.
HALtheWise 3y ago
The beauty of this method is that it doesn't matter. Even if YouTube generated sequential IDs, the researchers could still sample them fairly by testing random numbers.
- willsmith72 3y ago
  As long as the researchers' numbers were sufficiently random

Does YouTube generate video URLs completely randomly though? I'd be surprised if that was actually the case.

by paxys 3y ago

Does YouTube generate video URLs completely randomly though? I'd be surprised if that was actually the case.

timeagain 3y ago

Randomly, probably not. But I bet that they go pretty uniformly through their URL hashing space.

Dylan16807 3y ago

Anything random-ish will make this estimation method work. On either youtube's side or the measuring side. Why would they not be random? Nobody has ever found a pattern that I'm aware of, and there are pretty solid claims of past PRNG use. And a leak of the PRNG seed was likely why they mass-privated all unlisted videos a couple years ago.

jolyon 3y ago

Wait a second. If the IDs are all allocated in a contiguous block, and the author samples the whole space at random—then the estimate will converge to the correct value. If, on the other hand, the IDs are allocated at random, the estimate will also converge to the correct value. If you believe that there is some structure in YouTube video IDs, that would have no effect on this experiment. It would just reduce the fraction of the total address space that YouTube can use. This is a well-known property of "impure" names, and it means there is a good chance that the IDs have no structure. In other words, the video IDs would be "pure" names.

treesciencebot 3y ago
Is 32,000 a good enough number to estimate the entirety of the Youtube’s video space? It felt to little for what they are trying to accomplish (especially when they started doing year by year analysis)
- Dylan16807 3y ago
  When you're estimating a ratio between two outcomes, the rule of thumb is that you want at least 10-100 samples of each outcome, depending on how much precision you want. They got 10,000 samples of hits, and a huge number of samples of misses. Their result should be very accurate. (32,000 was a different number)
- cbolton 3y ago
  32000 is just the "cheat factor" by which they increase the method's efficiency. I'm not sure how much the "cheating" would affect the precision of the result. But assuming it has no effect, it's easy to estimate this precision: They found X = 24964 videos in a search space of size S = 2^64. For the number of existing videos they report the estimate N = 13,325,821,970. From this we can find their estimate for the probability that a particular ID links to a video: p = N / S ≈ 7.22e-10. So the equivalent number of IDs that they have checked (the number of checks without cheating that would give the same information) is n = X / p ≈ 3.46e13. Since X is a Binomial, its variance is Var(X)=n⋅P(1-P) (where P is the real proportion corresponding to the estimate p above). And N = X⋅S/n so its variance is Var(X)⋅S^2/n^2. The standard deviation of N is thus σ = S⋅sqrt(P⋅(1-P)/n). Now we don't know P but we can use our estimate p instead to find an estimate of σ! We find that the standard deviation of their estimator for the number of YouTube videos is approximately S⋅sqrt(p⋅(1-p)/n) ≈ 8.43e7. That's just 0.633% of N so their estimate is quite precise.

HALtheWise 3y ago

The beauty of this method is that it doesn't matter. Even if YouTube generated sequential IDs, the researchers could still sample them fairly by testing random numbers.

willsmith72 3y ago
As long as the researchers' numbers were sufficiently random