Show HN: Six Degrees of Wikipedia

Re:Show HN: Six Degrees of Wikipedia by jwngr on Monday February 26, 2018 @04:35PM (#16469180)

Thanks! I'm glad you asked. I actually do what I call a bi-directional breadth first search[1]. The gist of it is that instead of just doing a BFS from the source node until I reach the target node, I do a reverse BFS from the target node as well and wait until the two searches overlap. That helps with the exploding path problem, although that still becomes an issue for longer paths (>= 5 degrees generally). I also pre-compute all the incoming and outgoing links for each page when I create the database[2] so I don't need to do that upon every search, which resulted in a huge performance boost.

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

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by vorpalhex on Monday February 26, 2018 @05:09PM (#16469431)

When I was first playing with this, I actually really expected you to be using an expensive performant solution like neo4j. When I read that you were using sqlite, I didn't believe it at first and thought it was a mistype from dev until I looked over the source.

That's an impressive and well thought out performance enhancement, and that the app runs so blazingly fast on sqlite is very impressive.

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by sinaa on Monday February 26, 2018 @05:37PM (#16469622)

My thoughts exactly. It's impressive that despite relying on BFS, the tool manages to be so fast on a tiny node on google cloud. Even when there's a depth of >= 5 !

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by lbruder on Tuesday February 27, 2018 @07:01AM (#16472701)

Especially SQLite is often overlooked. A marvelous library that should be part of every personal toolkit.

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by matteuan on Tuesday February 27, 2018 @05:14AM (#16472312)

Neo4j is not necessarily more performant, especially for a particular use case like this.

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by nly on Monday February 26, 2018 @06:09PM (#16469830)

The downside of bidirectional seems to be that things like place names are linked via short paths through boring articles like "Census designated place" or "City"

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by jwngr on Monday February 26, 2018 @08:04PM (#16470356)

The bi-directional nature of the search does not change the end result. It is simply a performance improvement.

[ Parent | on HN ]

Re:Show HN: Six Degrees of Wikipedia by solarkraft on Tuesday February 27, 2018 @12:08PM (#16475439)

Still - It can be annoying. Maybe there could be an option to exclude articles with specific text/link ratios?

[ Parent | on HN ]