Mathematics at Google

Seeing PageRank discussed reminds me of a piece of fun trivia. The idea for PageRank came out of the success of the Science Citation Index, which ranks papers according to how often they have been cited. The idea of trying to study the structure of citations in academia came out of people who were inspired by a 1948 essay, <i>As We May Think</i>.<p>But that essay's main topic was an imagined technology called memex, to be implemented with an automated indexing system and microfilm. This technology is the first description of hypertext, which inspired multiple technologies. The second successful consumer application that I'm aware of that used hypertext was the web. (The first was HyperCard from Apple.)<p>Thus Google started as the application of one set of techniques inspired by <i>As We May Think</i> to a technology that was also inspired by <i>As We May Think</i>.<p>See <a href="http://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/303881/?single_page=true" rel="nofollow">http://www.theatlantic.com/magazine/archive/1945/07/as-we-ma...</a> for the essay itself. Do keep in mind that it was written one year after the transistor was invented, but the author already had 2 decades of experience with computing.

Look at the slide entitled Gmail (5), and compare the picture with the first graph on my blog post <a href="http://jeremykun.wordpress.com/2011/08/11/the-perceptron-and-all-the-things-it-cant-perceive/" rel="nofollow">http://jeremykun.wordpress.com/2011/08/11/the-perceptron-and...</a><p>It just goes to show, Google steals content without attribution just like everyone else.

The article has a section on the math used in Google Maps, which points to<p><a href="http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchies.pdf" rel="nofollow">http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchies.pdf</a><p>which says - there are 24 million places in the USA, connected by 29 million roads. You need 4 hours 15 minutes to pre-process this information. From then on, it only takes 7 milliseconds to find the shortest path from one place to another by running the Multilevel Query Algorithm, which is a souped up version of Dijkstra and runs 2000 times faster than Dijkstra's Shortest Path algorithm.<p>Is that right ? 24 million choose 2 is 288 trillion, so do an all paths search, then have a lookup table with 288 trillion entries, store that in HDFS, slap an LRU caching layer atop that, and you wouldn't have to run any graph query algorithm at all, so should be able to do much better than 7 ms ... just thinking out loud.

This is a fantastic publication! I do some part-time mathematics tutoring, and kids are always wondering where math is used in "real life". Since kids are all familiar with Google, this should resonate with them.

My mathematician friend pointed out that all that "research at google" requires "experience with large data sets and quantitative analysis". They want statisticians, not mathematicians.

My day-to-day programming consists so much of process and simple boolean logic that I hardly ever use math more challenging than 1 + 1 and 1 != 0. It's great to review how math can greatly influence the potential of your code.

Do they still heavily rely on PageRank? With the amount of traffic data Google has, I would expect more statistical approaches based on what users click (rather than graph algorithms based on how the web is linked) to be the backbone for ranking their results.