Get to the Point
A brief look into the technology that powers Google Maps
The US Library of Congress Geography and Maps division is home to some 5.6 million items. One of the maps on permanent display in the Library is Martin Waldseemüller’s 1507 map of the world (pictured above). The US government purchased the only known complete original copy of the map from Germany for a cool 10 million dollars in 2001, and it was officially presented to the library in 2007 by Angela Merkel — 500 years after its completion.
The reason the map is so highly valued is that it is the oldest known map to label the continents of the New World as America, in honor of Italian navigator Amerigo Vespucci. It was the first map to depict the world as having a Western hemisphere and a body of water distinct from the Atlantic ocean. That the world depicted in the map bears a comical dissimilarity to the world as we know it today deserves more than just amusement — to me it’s a reminder of how much we know about the world has changed in such a small period of time.
Frankly, it’s astonishing to me that the map is as accurate as it is. Just 15 years after Columbus’ voyage to the New World and cartographers already had a reasonable approximation of the South American coastline. Even after centuries of trading and exploration, the shape of the Asian subcontinent looks arguably even less accurate on this map. One can see how slowly information spread back in those days just from looking at some of the place names on the map. The by then century-old principality of Muscovy (modern-day western Russia) is still labeled Tartaria on the Waldseemüller map, which is a pretty glaring example of the German cartographer getting it wrong on his own continent. In his defense, moveable type had only been invented some fifty years earlier, and the majority of Europe would have illiterate at the time.
In 2007, the same year the Waldseemüller map turned half a millennium old, Google first released StreetView. I like to periodically remind myself that having such incredibly detailed information about the world at our fingertips is something each of us take for granted on a daily basis, and completely without precedent. Wave after wave of colonists and immigrants set sail for the new world knowing almost nothing about what awaited them there. Most people these days won’t even go to a restaurant without consulting photos, reviews, the menus and expected wait times.
They certainly won’t pull out a compass and try to find their way themselves. In fact, a night out in an unfamiliar city might start by opening up Google Maps and seeing which eateries are the closest, and then find the quickest way to get there. Even if you don’t consider yourself a map enthusiast, you probably rely on them every single day without even thinking about it.
While there are still many mapping applications available, eg Apple Maps, Bing Maps, Maps.me, Here WeGo, rome2rio (a favorite of mine), and even good ol’ MapQuest, I expect that “maps” has become synonymous with Google Maps for anyone born in this century, especially in the US. With all that in mind, here is an overview of some of the not-even-two-decades-old technologies that power Google maps.
Interface
Map software in the nineties and early aughts were particularly slow and clunky because of the limitations caused by “synchronous” rendering. Anyone who’s a millennial or older will remember how every link you would click on a page would cause a new page to load in your browser. That worked alright for navigating through sections of a site.
The genesis of Google Maps began with a 4-person Australian startup called Where 2 Technologies, which Google acquired in 2005. The team at Where 2 was interested in applying the emerging practice of Asynchronous Javascript and XML, or AJAX.AJAX allows for information to be updated in the browser without the need for a refresh and redirect, so users would be able to zoom in/out or scroll in different directions without having to refresh and reload the page every time.
The smoother user experience offered by Google Maps allowed them to quickly wrestle away market share from more established brands like MapQuest and Yahoo Maps. The android and iOS app versions of Maps launched in 2008, and by 2013 it was reportedly the most widely used app among smart-phone users around the world. Asynchronous rendering using javascript has since become the standard for web applications and is the primary reason for the shift to browser and cloud-based applications as opposed to having to physically install programs on a computer.
Satellite Data
Google also acquired the company Keyhole in 2005 for its Earth Viewer software, which has since become the application we know as Google Earth. This is the technology that creates a 3D globe model of the world from composites of satellite photos and aerial photography.
The imagery Google Earth uses comes from a few different sources, namely the USGS Landsat 8 satellite (launched in 2013) and a host of private companies like WorldView and QuickBird. Satellite data from the earlier Landsat 7 satellite, which suffered from a mechanical malfunction that resulted in gaps in the images. In devising a way to process the deformed images, Google also discovered an algorithm for extracting clouds from the images, which was a major improvement that we take for granted now. An article on TechCrunch posted in 2016 claimed that Google Earth imagery consisted of some 700 trillion pixels.
Road detail
Google works with federal and state governments to get maps of highways, rows and streets, but this data is further refined by the use of satellite data and Google Street View. In the process of capturing a 360-degree view of city streets, the Street View cameras also records an enormous amount of data that can be processed to confirm traffic directions, lane markers, speed limits, exits, business address locations, street names, bus stops, stop lights, bike paths and more.
Traffic
The third of Google’s important startup acquisitions in 2005 was ZipDash, a company that offers live updates of traffic patterns. As you probably suspected, the app also transmits data in real time GPS data from your mobile device, which is then analyzed and compared with other user data in order to update traffic conditions.
Public Transportation Infrastructure
Many public transportation systems offer real-time updates through easily accessible Application Programming Interfaces APIs which Google maps can also use to calculate trip times. This probably makes for the least reliable aspect of Google maps, however, since it makes the application reliant on external systems. I’m looking at you, WMATA.
Trip Calculation Algorithm
This is where my interest started for researching this post, and must be the most complicated function that the Maps app performs. I wasn’t able to find conclusive evidence but it would appear that this function is performed, at least in part, by using an A* (A Star) search algorithm. For a computer, simply calculating the distance between two points is a straight-forward operation, but most search algorithms don’t treat it as a matter of distance, but rather of cost. The “cost” incurred when making a trip, as far as the algorithm (and really anyone looking for directions) is concerned, is time.
When traveling somewhere, you know it’s always a good idea to move in the general direction of your destination, but you also know that optimizing that route comes down to understanding which roads will get you to your destination faster. You might choose a highway route that means more mileage from points A to B but at a faster rate; you might also choose to forego the highway because the traffic ends up doubling your travel time.
A search algorithm applied to finding the best route has to take the same tradeoffs into consideration. The A* algorithm works by treating each change along a path as a node. Think of a node as a place where you can make a change to your route: an intersection, an off-ramp, a subway stop, a bus station, etc. A road or a city block sidewalk is the node link connecting you to the next node in the network, like the next highway exit.
This handy animation illustrates what that node calculation looks like. An empty blue node represents the next available node connected to the nodes whose cost has been calculated, while a solid blue circle shows a node from which the only possible option is to return back along. The coloration of each evaluated node shows the distance of that from the goal. The greener the node, the closer the distance. If the costs of traversing two nodes is equal, the algorithm selects to continue exploring from the node that is closer to the goal.
In the real world, time is a much trickier thing to calculate than you would think. A “10-minute walk” depends on rate of speed you are walking, the number times you might have to wait at a cross-walk (and the duration of the light there), plus the elevation. A ride on a subway system might run on a schedule, may have express trains, might have varying expected wait times at transfer stations (plus the expected walk time between stations). Maps has become much better at keeping track of real-time traffic conditions, but in terms of estimating trip time before you start driving it is obviously much more accurate the shorter the trip.
3D Rendering
The three-dimensional rendering of buildings and terrain was recently expanded to the browser version of Maps, and after many years of refinement, the feature offers very detailed views of certain cities and places. Although this imagery is visible on the “Satellite” view of Maps, the higher-resolution images that show street-level detail actually comes from aerial photography, not satellite imagery. The photographs used to create the seamless birds-eye view are taken by planes making several passes to capture multiple angles of the ground below. The multiple angles can be combined and compared in order to create the 3D textures.
Full Circle
In 2018, the desktop version of Maps switched to displaying the Earth as a globe when fully zoomed out. The Mercator projection that Google had been using for more than a decade is almost as old as the Waldseemüller map (though not fully implemented until the 18th century), and was developed specifically to aid the sailors now regularly attempting to navigate the Atlantic ocean on their way to the new world. It bears reminding that this was a perilous and potentially months-long journey across open waters with no landmarks to orient by. By depicting lines of latitude and longitude at right angles, the Mercator projection makes it easy to use a compass to travel along a straight line drawn between two points on the map. Note that this is the simplest route to maintain a course along, but not necessarily the shortest. Especially as the line gets longer.
Since the Mercator projection displays the land masses of a three-dimensional earth on a two-dimensional image while faithfully preserving their shape. This is why Maps originally used the Mercator projection, as it made it possible to zoom in and out easily without having the image distort in the process.
Any 2d projection of the world is going to have its drawbacks. Globes have been around for as long as the earth has been understood to be round, since at least the second century BC, and are clearly the best way of representing the earth’s geography, but in comparison with a map, a globe is more costly to create, more difficult to transmit, and not practical to scale. A large map in a classroom, for instance, occupies almost no space.
The glaring flaw in this projection is that, while the shape of countries is preserved, their relative size becomes significantly exaggerated at the Earth’s poles. Most notably, Greenland appears roughly the size of Africa on the Mercator projection, when its area is only about 7% of Africa’s. Alaska looks like it could cover half of the US, but is roughly a fifth the size. And Russia looks like a completely different country.
The globe view bridges the gap between geographic fidelity and easy of navigation. I think this feature of Maps, while perhaps not on the same level of technical achievement as some of the others, is really an important one. The maps we use to orient ourselves in the world are longer a static two-dimensional representation of the Earth, but are now a carefully and continuously curated three-dimensional interactive object which can as accurately depict its true shape as offer us the best route to get where we’re trying to go. You may only consult a map these days for directions to something a few miles away, but remember to zoom out every now and again.
