On-demand page scrape + memoisation is almost certainly a win here. Even if thousands of people are hitting this, a lot will choose some of the same queries (I'm sure Kevin Bacon and xkcd and philosophy are in there a bunch), especially in the tails of the paths (Latin, Mathematics, ...)