News for hackers. Stuff that matters.

A comment on Show HN: Six Degrees of Wikipedia. Parent comment

Re:Show HN: Six Degrees of Wikipedia by jwngr on Monday February 26, 2018 @03:10PM (#16468542)
I think this is going to be extremely computationally intensive. One of the big performance wins I got when designing the search algorithm[1] was visiting as few nodes in the graph as possible (which I did via a bi-directional breadth-first search). To find the most distant node, I'd need to traverse the entire graph, which consists of almost 6 million nodes. It can be done, but it would take minutes, hours, days, ...

[1] https://github.com/jwngr/sdow/blob/a2699dc95d884ec64a4641630...

[ Parent | on HN ]
Re:Show HN: Six Degrees of Wikipedia by AstralStorm on Monday February 26, 2018 @03:36PM (#16468758)
Not too expensive, you can use parallel IDDFS to get a good approximation quickly. (Especially if you pick a good heuristic to follow links.)

Challenging part is keeping track of already visited pages to break cycles - some variant of a Bloom filter will help.

[ Parent | on HN ]