Mathematics at Google

Vannevar Bush's ideas about information organization and consumption in the future were eerily accurate. Reading about the history of Memex and the roots of the Information Architecture field in general is something I highly recommend for anyone interested in Information Science, etc.

Someone just started a discussion: http://news.ycombinator.com/item?id=4577865

Wait, they just used your graph and didn't even contact you about it?

It's one guy who happens to work for Google, rather than the whole company.

I am trying really hard to ignore the Futurama picture. Really hard!

Good luck precomputing all those pairwise shortest paths. Storing the table might not be too bad. But standard algorithms like Floyd-Warshall are O(n^3) in the number of vertices. There are faster algorithms based on fast matrix multiplication but the precomputation time would still be prohibitive. Keeping it up to date would be even worse. The construction of a new highway could require updating the shortest paths for an enormous number of pairs.

The economic argument would go like this: The revenue generated from your maps business is proportional to the number of queries actually processed, not the total number of conceivable queries. The queries processed is such a tiny subset of the possible queries that you want your computational expenses to track the former, not the latter.

With a hierarchical shortest paths algorithm, you can still precompute all pairwise shortest paths at the coarser level. For road navigation you might precompute the shortest path between every pair of interstate highway exits in the USA like this paper is doing. In an open-world game like Skyrim you might precompute the shortest paths between all towns and other major hubs and points of interest. That might not yield truly optimal paths. For game use it's close enough and has the benefit of corresponding to how humans naturally navigate.

Sidebar: The old Crash Bandicoot games used precomputed shortest paths in a neat way. Their navigation was based on a triangular mesh, so every triangle had up to three edgewise neighbors. Thus for a navmesh with n triangles, they needed lg(3) n(n-1)/2 <= n(n-1) bits to store the table. For convenience they probably stored this in a redundant form requiring 2n^2 bits = n^2/4 bytes. But with only 64KB of additional memory, this still let them support 512 navmesh triangles per level with lightning-fast path finding.

...and use up tons of hardware when you can get by without doing that?

I'm not a googler but I do know a bit of Math and Statistics and many of the approaches they take can be cleverly reduced to optimization problems or matrix math both of which are more the domain of applied mathematicians then statisticians.

> simple boolean logic

A SAT solver[1] can automatically figure out a range of acceptable solutions for your conditions. 'I want this goal, is there a way to make that happen?' Security people love this. SMT solvers are even crazier[2] and can automatically determine solutions to linear equations or inequalities (this comes in handy when analyzing loops). Z3 has an online version at [3].

Also, if you have a lot of nasty cascaded if-statements, a K-map[4] and espresso[5] can reduce those down to a minimal set of branches. Note that fewer branches means fewer branch prediction penalties, which means faster code!

[1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

[2] http://media.tumblr.com/tumblr_m8ywn1iesH1r6uu3b.gif

[3] http://rise4fun.com/z3/tutorial/guide

[4] http://en.wikipedia.org/wiki/Karnaugh_map

[5] http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/in... and ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz

My experience is that people who are aware of opportunities to use math find them. And people who are not aware conclude that they weren't really there.

For example are you a web developer? Have you started using A/B testing yet? If yes, that's math. If no, then you are in a position to make your employer a substantial amount of money.

For another example my very first project in my first programming job required me to build a set of canned reports. There was one user request which turned into, "We want to do this, but don't know if it is possible." I wound up using inclusion-exclusion techniques that I'd learned in grad school to solve that problem! (The problem was how to ship a local database without detailed information they shouldn't have about the rest of the company, and yet still be able to present reports comparing themselves to the rest of the company. And those reports had to drill down. So if you were responsible for 5 sites you'd be able to generate those reports for everyone that you could see, or for each site individually.)

PageRank is definitely still used, although it's doubtfully the sole determinant of ranking results. See http://jeremykun.wordpress.com/2011/06/21/googles-page-rank-...

It's a closely guarded secret but at the very least we know that every page is annotated with many different signals, which are combined with magical secret sauce.

i'm always disgusted when a googler publishes anything about pagerank. yes, google is still using links as a single in their search result, but the original pagerank paper is from 1998, we can sure as hell be sure that they iterrated/rewrote it a few thousand times since then.

every time a (any) googler now publishes a paper (or presentation) about (the old) page rank a horde of too well paid SEOs is pointing to it for the importance of pagerank, and why linking out is bad, and whatever bullshit (i.e.: later in this thread the based on nothing hypothesis about "nofollow") they come up with. everytime it happens, the SEO bullshit dance starts anew. (in my opinion pagerank is thought-cancer, please see my old TC article for more about this http://techcrunch.com/2010/07/07/startups-linking-to-your-co... )