Reconstruct full BFS tree from truncated representation about youtube-recommendations HOT 3 CLOSED

bb3ae0d takes a first pass at this. Seems to work as expected, reasonably efficient (~3 seconds per tree using our most recent params), but needs further testing.

from youtube-recommendations.

(The markdown document mixing_analysis was the initial motivation for this issue, and gives some more colour on why we might want to reconstruct the full BFS tree)

from youtube-recommendations.

48866ab adds scripts that deal with the above. Will likely need miscellaneous fixes, but closing this issue since the central problem has been solved.

The logic of the script is as follows: suppose we are at depth n. Some subset of the videos at depth n were visited at some depth n' < n, so as described above we do not follow those edges in our crawl. Consequently if such a video is listed in the recommendation column at depth n, it would not appear as in the video_id column at depth n + 1. Continuing with the example above:

a
|
|--a
|
|--b
   |--c
   |--d


a|a|0
a|b|0
b|c|1
b|d|1

The list of recommended videos at depth 0 is [a,b], but the (unique) videos we have in the video_id column for depth 1 is [b]. Taking the difference between these lists, we see we need to add a record for a. So our script would:

• scan over the depths in an outer loop
• at depth n take a list difference between the video_id column for depth n and the recommendation column for depth n - 1: these are the videos we truncated.
• iterate over the truncated videos, looking up their recommendations at whatever depth they were first encountered, and appending the appropriate records to the table.

Things become more complicated when we reach our sampling depth, and constituted the biggest headache in addressing this issue. Can give more colour on this if people are interested (/ if there's anybody else reading this).

from youtube-recommendations.