Google Maps Doesn't Store Your Route. It Stores Something Smarter.

You put Paris in one field and Rome in the other, press directions, and the route is there. Nobody thinks about it. It is one of those things a phone does so reliably that it stopped registering as a thing being done at all.

The first version of that sentence, in my notes, said the route appears while you are still typing. It doesn't. Type one city on its own and Maps drops a marker on it, and that is all that happens. The route exists only once you ask for directions. That detail matters later, because the whole answer here is about what got finished before you asked.

The Directions button is the thing worth watching. Everything measured in this article starts from the moment it is pressed, not from the moment the two names go in.

So here is the question I actually wanted answered, and it is not the one about how the search is made fast. It is the lazier one. These companies have the whole map, and they know every question anybody can possibly ask, because every question is a pair of points on a map they already hold. Why not work out all of the answers ahead of time, store them, and turn every request into a lookup?

It sounds cheap. It is not. Working out how expensive it actually is turned out to be the fastest way into how routing works, because the number that kills the idea comes from the same source that supplies the thing they do instead.

Two things I am not claiming. Google has never published how Maps finds a route, so none of this is a description of Google's internals; it is the class of technique used by the systems that do publish, measured by people who published the measurements. And this is about finding the road, not about predicting the traffic on it. Traffic has its own published answer and it is a separate mechanism. It is not in here.

The honest way, and what it costs

Start with doing it properly. You need a price to compare against.

A map, to a computer, is a pile of intersections and the roads between them, where an intersection is every place two roads meet and each road carries a number, roughly how long it takes to drive it. That is the whole data structure. The map used as the benchmark below is Western Europe: 18.0 million intersections and 42.5 million roads.

The honest search works like this. Stand at your starting intersection. Repeatedly take the cheapest road you have not taken yet, from anywhere you have already reached, and note the arrival time at whatever intersection it lands on. Keep going until you have arrived. It always gives the true quickest route, and there is no cleverness in it whatsoever.

The shape it makes is a flood. It spreads outwards in every direction from where you started, including backwards, away from where you are going. It has to. Until you have actually arrived somewhere, you have no way of knowing whether that direction was useful. And the flood is not a metaphor for the cost. The flood is the cost: every intersection the water touches is one the computer had to look at, price and file.

The search spreads from Paris in every direction, including away from Rome. Every intersection the colour reaches is one that had to be looked at and priced, which is where the nine million comes from.

Which brings in the numbers, so it is worth saying where they come from. There is a 2015 research survey, Route Planning in Transportation Networks, that collects the main routing methods and measures all of them on one map, on one machine, with one query set. That last part is what makes it useful. Anybody can quote a speed for one algorithm. A survey that runs the alternatives side by side is what lets you say an approach is worse than another one, rather than faster than a story you heard.

Every figure in this article comes from one table in it, Table 1. Not because there was nothing else to read. Mix a number from a different paper into this comparison and the comparison stops meaning anything.

On that map, the honest flood looks at 9,326,696 intersections for a single trip. That is 52% of Western Europe, examined so that one person can drive to one place. It took 2.195 seconds.

Those two seconds are one core of a single server processor from 2010, running one query. It is not a measurement of your phone, and not of anybody's datacentre. Hold onto the ratios instead of the absolute times. Ratios survive hardware getting faster, because everything in the comparison gets faster together.

One more thing about how the queries were picked, because it constrains everything after it. The survey chooses pairs of points uniformly at random across the whole map. In practice that means long trips: Portugal to Poland, not your house to the supermarket. Every figure here is about the hard case.

Aim it, then search from both ends

Everybody's first instinct is to aim. You know roughly where Rome is, so push the search towards it and let it ignore the roads heading the other way. It is such an obvious improvement that it has a whole literature.

On road networks it mostly does not work. The survey's own words are that the bounds are poor and the performance gain is small or non-existent, and there is no figure in the table for it, so I am not going to invent one. The reason is worth having, though. The only thing you can cheaply know about a place you have not visited is its straight-line distance, and straight-line distance is a terrible predictor of driving time. A motorway that swings the wrong way around a mountain beats a lane pointing straight at your destination. The aiming has no way to know that until it has driven both.

Aiming barely narrows it. Those two phrases are the survey's whole verdict, and this is the only step in the article with no measured figure to put beside the words.

The second instinct works better. Run two floods, one from Paris and one from Rome, and let them grow towards each other, because two half-sized floods really are cheaper than one full-sized one. The table agrees: 4,914,804 intersections, against 9.3 million.

That is a genuine improvement. It is also still nearly five million intersections, for one person going on one trip.

Two half-sized floods are genuinely cheaper than one full-sized one. Cheaper is not the same as cheap, and the pair of them still reach nearly five million intersections.

So stop searching

The rearranging has now been tried and it has bought a factor of two. The obvious move is to stop rearranging and start remembering.

This is the idea I opened with, and it deserves to be taken seriously rather than waved away, because precomputation, the general name for doing work before anybody asks for it, is one of the strongest moves in the subject. You pay once, in advance, on your own hardware, at a time when nobody is waiting. Every user afterwards gets the answer for free. It is why a database has indexes and why a compiler exists. Routing looks like the perfect candidate, too, because the set of possible questions is not open-ended. It is every pair of intersections on a map you already hold.

So: work out the quickest route between every pair, store the answers in one enormous table, and answer each request with a lookup.

The survey costed it. As a query it is spectacular, because looking up an answer you already have is close to the fastest thing a computer does: 0.06 microseconds, and a microsecond is a millionth of a second. That is around 36 million times quicker than the flood, and comfortably the fastest row in the table. The problem is everywhere else.

one long trip, on the same map
  honest search    9,326,696   2.195 s
  from both ends   4,914,804   1.206 s
  stored answers           -   0.06 us

Building that table takes 145 hours and 30 minutes, a shade over six days of computing. And it needs 1,208,358.7 GiB to hold. That is over a million gigabytes. The survey's verdict on the idea is one word, impractical, since it would require more than one petabyte of memory, and a petabyte is that same million gigabytes under a tidier name.

Every answer worked out in advance, one line per pair of points, until the map vanishes underneath them. The two figures on the right are what that pile costs to build and what it costs to hold.

I want to be careful with that six days. It is the number here that is easiest to file under the wrong idea, and I had it filed wrong myself for a while. Six days is the cost of the approach that gets rejected. It is not what the technique below spends preparing a map. Keep it attached to the storage plan. The real preparation bill turns up later and it is nothing like this.

Where a million gigabytes comes from

A million gigabytes is one of those quantities that stops meaning anything. So I did the arithmetic to see whether it was even the right shape. It is, almost exactly, which is a good sign about the source.

Every pair of intersections needs one stored answer. There are 18 million intersections, so there are 18 million times 18 million pairs, which is 324 trillion. Give each one four bytes, enough to hold a travel time:

pairs   18,000,000 x 18,000,000 = 3.24e14
bytes   3.24e14 x 4             = 1.30e15
GiB     1.30e15 / 1024^3        = 1,206,994
paper                             1,208,358.7

That is within a tenth of a percent of the published figure, and the gap is that the map holds a shade over 18.0 million intersections rather than exactly 18.0 million. GiB is the binary gigabyte the paper uses, 1024 to the power of three bytes. In the decimal gigabytes you see on a hard drive, the same pile is about 1.3 million. The four bytes is my assumption rather than something the paper spells out. It is the assumption that reproduces their figure, which is the only reason to trust it.

Two things fall out of that arithmetic, and both matter more than the size does.

The first is that it is not a storage problem you can shop your way out of. The table is about three million times the size of the map it is answering questions about. The map is 0.4 GiB. Everything the table knows was derived from that 0.4 GiB, and it needs a petabyte to say it. Nobody is buying that much memory per continent. Moving it to disk removes the one property that made the idea attractive in the first place, which was that a lookup is instant.

The second is quieter, and I am planting it here because it comes back at the end. Four bytes per pair buys a travel time. It does not buy the route. A number is not a line on a map. If you want the actual list of roads you either store that as well, which is enormously bigger than one number per pair, or you work it out when asked. The survey is explicit about this: the queries it measures compute the length of the quickest path, not its list of roads, and the space column leaves out the data needed to unfold a path. That holds for every row in the table, including the row that turns out to be the answer.

The thing nobody in that list has touched

So rearranging the search does not get you there, and storing the answers cannot be paid for. Look at what has actually been varied so far: the direction the search spreads, the number of ends it runs from, and whether it runs at all.

Every one of those is a change to the search. Nobody has touched the map.

Everything tried so far was a change to the search. This one changes what is being searched, and it starts at a junction nobody would ever name.

Watch on YouTubeGoogle Maps Doesn't Search the Map You SeeThe same mechanism as a video, following one junction as it is folded out of the map and replaced by a road carrying the exact travel time of the path it stood on.

One crossroads on the edge of a town

Go all the way in, to somewhere with nothing interesting about it. A small crossroads on the edge of a town, one road arriving from a neighbouring junction, one road leaving towards another. Say the way in takes nine minutes and the way out takes eight. Those two numbers are invented, for the sake of one clear example. The map has 18 million of these places.

Long before anybody asks for a route, this crossroads gets set aside. Setting it aside would break every journey that ran through it. So at the same moment, a new road is drawn straight from the first neighbour to the second, labelled with the time of the journey that used to go through the middle. Nine plus eight. Seventeen minutes.

Watch the dot in the middle. It goes grey rather than disappearing, which turns out to be closer to the truth than the word I have been using for it.

Anybody driving from the first neighbour to the second is still told seventeen minutes, because seventeen minutes is exactly what it took the old way. Nothing was rounded and nothing was estimated. No real travel time changed. That is the property the whole technique rests on, and it is worth saying plainly. “Make the map smaller” normally means “make the answers worse”. Here it does not.

The version above is the simplified one, and the simplification sits in a single word. The new road gets drawn only where the path through the middle really was the unique quickest way between those two neighbours, and if there was already an equally quick way round, nothing needs adding, because nothing would be lost. That word is load-bearing. It is the difference between a map that sprouts a new road at every junction and one that stays roughly the size it started.

The third path arrives with no time on it, only the word slower, because the only question being asked was which side of seventeen minutes it fell on. Nothing in the rule needs to know by how much.

Do it eighteen million times

One junction changes nothing. So it happens to the next one, and the next, all the way up.

The order is the interesting part. It works from the least important intersections upwards, and importance here is something the preparation works out for itself rather than reads off a road sign. Picture dead ends going first, then residential streets, then the small roads between towns, with the long-distance roads last. That ordering is an illustration rather than something the survey states. What it does say is that intersections are ordered by importance and taken out from least important to most.

What is left standing is a skeleton. A thin web of long roads spanning the continent, each one standing in for thousands of small ones underneath it, each carrying the exact time of the path it replaced. Your street is not on the skeleton. Neither is mine.

The pieces that survive to the end are the long ones, which is why what is left looks like a motorway map with everything else stripped out. The note on screen is there because the exact order shown is an illustration.

The word I need to take back

I have been saying that junctions get taken out of the map. That is the picture. It is not what happens to the finished thing.

Nothing is taken off the map. The survey's phrasing is that an intersection is temporarily removed, and the temporarily is load-bearing, because the removal happens during preparation while the new roads are being worked out. The finished map still holds all 18 million intersections and all 42.5 million roads.

What each one gained is a rank, a number saying how important the preparation decided it was, and the rule attached to that number is the entire trick: a search may only ever move to an intersection of higher rank than the one it is standing on. That is the cost the word arrives with. Your street is still there, fully drawn, with its real travel times on it. Your search simply never goes down to it, because down is not a direction it is allowed to move.

Nothing was removed. The small streets are all still there, each carrying a rank, and the rank is the thing your search is never allowed to move down to.

This is also why nothing is lost. The small roads have not been approximated away. They have been made unreachable from above, in a way that cannot change any answer, and that is a far stronger guarantee than a simplified map.

Five minutes, and no extra space

Preparing the whole of Western Europe this way takes five minutes on one core, on the same machine that needed 2.195 seconds to answer one query the honest way. It happens once, for everybody, before anyone asks for anything. The finished thing occupies 0.4 GiB, which is the same figure the table gives the plain, unprocessed map.

what preparing it costs
  stored answers   6 days   1,208,358.7 GiB
  shrunken map     5 min            0.4 GiB

Put those two rows next to each other and the answer to my original question is sitting right there. Precomputing every answer costs six days and a petabyte. Precomputing the right structure costs five minutes and no extra space worth mentioning. Both are precomputation. One is trying to remember 324 trillion facts; the other spends five minutes rearranging 0.4 GiB so that almost none of those facts ever get looked at.

There is no pile of stored answers in there. That is the part I found genuinely surprising. The storage idea is not only unaffordable, it is unnecessary.

The pile of stored answers appears for a moment and is wiped away, because the finished thing does not contain one. It occupies the same space the plain map did.

Two hundred and eighty intersections

Now ask for the route.

From the Paris end the search only ever climbs. Off the local street onto a bigger road, off that onto a bigger one again, up onto the skeleton. From the Rome end the same thing happens backwards. Two small climbs, from opposite ends, and somewhere up in the long roads they run into each other.

They do not stop at the first touch. The place where two searches first meet is not necessarily the meeting point of the best route, so both carry on a little past it until nothing better can turn up. That detail gets smoothed out of explanations because it makes a clean picture messy, and skipping it would make the algorithm wrong rather than simplified.

Both searches only ever climb, and both carry on past the first place they touch. The lit junction is where the best meeting point turned out to be, which is not the first one either search found.

When it settles, that search has looked at 280 intersections. Same map, same kind of trip, where the honest flood had to reach 9,326,696.

intersections looked at, same map
  honest search      9,326,696
  from both ends     4,914,804
  shrunken map             280

That is about 33,000 times fewer, and it takes 110 microseconds, or 110 millionths of a second, which on the one core that needed 2.195 seconds per route the honest way works out at roughly nine thousand routes every second.

The old flood is still there behind, drawn at the size it needed. Note what the label on the meeting point says: two hundred and eighty buys the travel time, and the drawn line is extra.

And now the thing I planted earlier. Those 280 intersections buy the travel time, not the drawn line. The survey's measured queries compute the length of the quickest path and not its list of roads, and its space column leaves out the data needed for unpacking a path. Turning that answer into street-by-street directions means unfolding each long skeleton road back into the small roads it stands in for. That is more work on top of the 280. It is a small amount of work on a path already known to be the right one, which is a very different problem from finding it. But it is not free, and 280 is not the whole bill.

That is the same sentence that killed the storage plan, arriving a second time. Four bytes per pair is a travel time and not a route. 280 intersections is a travel time and not a route. The cheapest thing to compute about a journey is how long it takes, and the line on the screen always costs extra.

What this is actually a lesson in

The technique has a name, contraction hierarchies. I left it until the end on purpose, because the name explains nothing and the crossroads explains everything. It is worth knowing only so that you can go and search for it. The survey is Route Planning in Transportation Networks, arXiv 1504.05140, and Table 1 is the whole of the argument above.

What I came away with is a corrected instinct about precomputation, because I had been treating “work it out in advance” as one idea with a single dial on it, where the only question is how much you are willing to store. It isn't. Storing every answer and restructuring the data so the answers get cheap are both precomputation, they sit next to each other in the same table, and they differ by a factor of three million in space. The expensive one is the one that sounds obvious.

So the next time something on a screen answers faster than it has any right to, the interesting question is not how fast their machines are. It is what somebody finished before anyone asked, and whether they were smart about what they finished.

One gap I cannot close on my own. Every number here is Western Europe with randomly chosen pairs of points, which means long trips across a continent. The survey has nothing to say about a five-kilometre hop across a city, and I would expect the ratios to look quite different when the whole journey happens below the skeleton. If you run one of the open routing engines locally, OSRM or GraphHopper or Valhalla, send one long cross-country query and one short urban one on the same region. Tell me the query times it reports, and which engine and region you used. That is the comparison I have no way to make from a 2015 table.

🎉 Enjoyed this article? Your support means the world to me!

🎬 Subscribe on YouTube for video versions of these posts: https://www.youtube.com/@swift-pal

💼 Let's connect on LinkedIn for more professional insights: https://www.linkedin.com/in/karan-pal

☕ If this saved you some time, you can buy me a coffee: https://coff.ee/karanpaledx