jwngr

I'd prefer you not send any additional load to my server (this is just a side project I'm paying out of pocket for), but you are welcome to download the data yourself. There are instructions in the project README[1] to download the SQLite files I use in the project and I should have documented enough about the schema for you to know what queries to make. I am happy to answer questions via GitHub issues if you have them.

[1] https://github.com/jwngr/sdow#get-the-data-yourself

The full fact list is on GitHub[1]. The fact list was a lot more interesting and important when searches took longer to run. One of the bad things about improving the performance so much was the fact that the facts don't have as long to display :P

[1] https://github.com/jwngr/sdow/blob/master/website/src/resour...

It was down for a little while due to the traffic but it's back up and running again.

The autocomplete suggestions hit the live Wikipedia API[1]. The actual search algorithm is on a dump of Wikipedia[2], which I plan to update monthly.

[1] https://github.com/jwngr/sdow/blob/f39398d112fecf7b993c64bd4... [2] https://github.com/jwngr/sdow#data-source

The resulting SQLite database file is currently 8.3 GB, most of which is taken up by the `links` table. The big performance wins are having a handful of indexes (see the .sql files[1] for the database's schema) and preprocessing a lot of data so I don't have to do duplicate work every time a query occurs. For example, instead of the `links` table going from `source_id` to `target_id` and having a ton of rows which have the same `source_id`, I go from `id` to `outgoing_links` (which is a |-separate string of all source page IDs). Computing each page's incoming and outgoing links is the really heavy work and I only do that at database creation time, using a beefy GCP machine with 8 vCPUs, 52 GB RAM, and a 256 GB SSD. It still takes about an hour, but it's a one time cost and means I can run the actual service on a much smaller machine which won't cost me a fortune to maintain. Also, SQLite is just very fast and performant out of the box, so as usual, it's a matter of choosing the right tools for the job.

[1] https://github.com/jwngr/sdow/tree/master/database

So the reason is that "Theodore Roosevelt" links to "Freddy Fazbear" (ctrl+f for "Articles related to Theodore Roosevelt" and then click it and then click "Teddy Bears") which redirects to "Friday Night at Freddy's". So, technically, there is a direct link there, albeit through the categories dropdowns. Unfortunately, Wikipedia doesn't have anything in their database dumps identifying if a link is in the article itself versus the categories dropdowns or sources, so I include them all.

Check out an earlier comment I made[1] which has some information about this. It also includes links to the relevant code, which is all open source.

[1] https://news.ycombinator.com/item?id=16469260

The sheer scale of Wikipedia (5 millions pages, half a trillion links) made it difficult to make the searches fast. Simply downloading the Wikipedia database dumps and parsing them into my own database took over a day on my first successful attempt. The site returns most results in just a few seconds despite the giant graph size.

Thanks, glad you enjoyed it!

> I was expecting the site to tell me how to start at page X and get to page Y with the min number of clicks.

Yup, this is exactly what the site does, and a bi-directional BFS is an efficient way to do it. The special thing about my bi-directional BFS is that I follow outgoing links when searching from the source page while following incoming links when searching from the target page[1].

> I did notice that someone pointed out that they get different results by swapping the order of X and Y. This seems pretty surprising?

This is expected, because it is a directed graph, with the links on Wikipedia being in one direction. Just because page A links to page B doesn't mean page B links to page A.

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

Ooh cool idea! That certainly would improve the information density issue. I honestly never considered that at all and have no idea how I'd do it in d3, but I may try to hack it out. Thanks!

Thank you! The graph is built using vanilla d3, no library on top of it. The code for it lives all in one file, ResultsGraph.js [1]. I pieced together the code from a handful of other attempts online. I am still not 100% pleased with the performance of it with a larger number of nodes (250+), but that seems to be a common complaint with the d3 force simulation layouts.

[1] https://github.com/jwngr/sdow/blob/master/website/src/compon...

I do a bi-directional BFS, but the search from the target node traverses incoming links as opposed to outgoing links. That's why I have to store both in the `links` table[1].

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

The graph is most definitely directed. One small example is Facebook -> Narcissism (1 path of 1 degree)[1] compared to Narcissism -> Facebook (8 paths of 2 degrees)[2].

[1] https://www.sixdegreesofwikipedia.com/?source=Facebook&targe... [2] https://www.sixdegreesofwikipedia.com/?source=Narcissism&tar...

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

Very cool! Your UI is great. I like all the animations and the graph is super smooth. All my code is open source[1] and it is decently documented. I'm happy to answer any questions you have and you're more than welcome to use any of the code I wrote for your project.

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

I just added the query string stuff in the URL this morning and didn't even think about this issue. Just made the change as you suggested[1]. Thanks!

[1] https://github.com/jwngr/sdow/commit/b9164b4455661d7775aeb78...

This has been fixed[1] and should behave in a more intuitive way now. Thanks for the suggestion!

[1] https://github.com/jwngr/sdow/commit/6e42e06488a592784e5d3d2...

I'm not sure caching would help a ton given how I structure the data and do my searches in batches of pages, not for individual pages. I already do some "caching" by precomputing all incoming and outgoing links for each page when I create the database, which, as you would expect, yields a huge performance improvement. A cache certainly would help, but I would expect the hit rate on it to be extremely low, making it not worth the effort. I may have a different opinion after analyzing some of today's results though. Thanks for the suggestion!

Thanks a lot for sharing! BTW, I just fixed the confusing interaction with the text input placeholders[1].

[1] https://github.com/jwngr/sdow/commit/6e42e06488a592784e5d3d2...

Just implemented this with a quick hot fix[1]. Hopefully I didn't break anything else in my hurry to get out.

[1] https://github.com/jwngr/sdow/commit/6e42e06488a592784e5d3d2...

I'm storing all the search results and will do some analysis on the data. Maybe I'll even get around to adding a new page with some of the interesting stuff I find.

I actually had a friend suggest it to me and the Neo4j docs happen to be one of the many tabs I currently have open. I was already so far into using SQLite for this project and I wanted to ship it, so I decided to stick with what I had. I would be interested to see how Neo4j performs with such a big dataset (the resulting SQLite file is around 9 GB with nearly 6 million nodes and 500 billion links). I was a bit worried that Neo4j wouldn't be able to scale to a graph of that size, but that is a completely untested and ignorant opinion. If you have any experience with Neo4j, I'd love to hear your thoughts.

I never actually touch any of the source HTML. I think that would simply take way too long and would probably result in some very high bandwidth charges. I use three tables from a public dump of Wikipedia's database, which unfortunately don't differentiate between where the links occur on the page. Check out the first section of my README[1] for more information.

[1] https://github.com/jwngr/sdow#data-source

Good suggestion! I intended to have that exact button, but couldn't find a way to put it in the UI without making things more confusing. I expect I'll add it in the future. Thanks for the suggestion!

No, not an idiot. I didn't use the best terms. I updated them to say "Web (frontend) hosting" which are my static files (the HTML, JS, CSS) which is deployed to Firebase Hosting and "Server (backend) hosting" which is my backend Python Flask web server which is deployed to Google Compute Engine (GCE).

So, the website files are hosted on Firebase while the backend is hosted on GCE. The database is actually not hosted; it's just a SQLite file stored on my GCE instance.

Thanks! It's weird, but as soon as I tried upgrading to an identical GCP machine running Debian 9 (stretch) and run my database creation process[1], it took many, many times longer to even download the several GB dumps from Wikipedia via wget than it did on Debian 8 (jessie). As the beefy machine I use for the database creation process costs ~40 cents per hour, I figured it wasn't worth it to upgrade to Debian 9 since the Debian 8 machine finished in one hour and worked fine. After trying it a second time a month later and realizing the same thing happened, I added a note for myself in the README about it. I did find some other reports about it online[2] and just decided it wasn't that critical to upgrade it at the moment.

[1] https://github.com/jwngr/sdow#database-creation-process [2] https://lists.debian.org/debian-kernel/2017/12/msg00265.html

The database creation script[1] has a lot of Unix junk in it, but reading through the comments and echo statements should give you an idea of what it does. The end result is a SQLite database with a size of about 9 GB which has four tables, the schema of which are described in the README[2]. The big things that are precomputed are redirects are "auto-followed" to reduce the total graph size and all incoming and outgoing links are stored in a |-separated string for each page (in the `links` table).

Every time a query is made, a bi-directional breadth-first search[3] is run which uses the |-separated incoming and outgoing links and runs a fairly standard BFS algorithm. A lot of the hard work was precomputed, which minimizes the number of required database queries and makes each search respond fairly quickly.

[1] https://github.com/jwngr/sdow/blob/master/database/buildData... [2] https://github.com/jwngr/sdow#database-creation-process [3] https://github.com/jwngr/sdow/blob/master/sdow/breadth_first...

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...

Yes, definitely a feature I'd like to add. I can change the opening the page on Wikipedia to happen on double click instead of single click. I am still a d3 noob and need to figure out how to implement the highlight path thing.

This is an interesting question that I'd like to answer now that I have all the data. I am curious to see how long it will take to find a solution as I believe even the most efficient algorithms for this have a high runtime complexity.

And yes, the graph is not connected (there are both nodes with no outgoing links and with no incoming links), but over 99% of the pages are connected, so the answer would still be interesting and worthwhile.