sdow

Hey everybody, my "Show HN: Six Degrees of Wikipedia" [1] from two weeks ago was really popular with this crowd and I enjoyed all the comments and discussion that resulted. Now that the site has handled half a million search results, there is a lot of interesting data which I know you will also enjoy seeing. So I put together this blog post and I plan to make a series of them on different aspects of this side project. All the code for my project is open source [2] and I'm happy to answer any questions or hear any suggestions you've got. If you want to get notified of future blog posts in this series, I have a low-volume personal newsletter [3] you can sign up for. [1] https://news.ycombinator.com/item?id=16468196 [2] https://github.com/jwngr/sdow [3] https://jwn.us15.list-manage.com/subscribe/post?u=d19fa80c86...

Hey everybody, my "Show HN: Six Degrees of Wikipedia" [1] from two weeks ago was really popular with this crowd and I enjoyed all the comments and discussion that resulted. Now that the site has handled half a million search results, there is a lot of interesting data which I know you will also enjoy seeing. So I put together this blog post and I plan to make a series of them on different aspects of this side project. All the code for my project is open source [2] and I'm happy to answer any questions or hear any suggestions you've got. If you want to get notified of future blog posts in this series, I have a low-volume personal newsletter [3] you can sign up for. [1] https://news.ycombinator.com/item?id=16468196 [2] https://github.com/jwngr/sdow [3] https://jwn.us15.list-manage.com/subscribe/post?u=d19fa80c86...

Possibly... follow this GitHub issue[1] if you want to be notified about it. [1] https://github.com/jwngr/sdow/issues/11

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

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

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

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

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

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