In an era where every turn, intersection, and shortcut matters, Google Maps stands as the leader in navigation technology. The algorithms, databases, and real-time data that power this application helps users move around the world.
This article will delve into the system design of Google Maps Routing Engine considering its product and technical requirements.
Main Idea
At its core, Google Maps maps places and tracks users. With this, the application offers features like routing and finding nearby restaurants. These functionalities are enabled using graph algorithms, artificial intelligence, and real-time data as shown below.
Finding the Optimal Route
Let's start simple: How would you find an optimal route between a given source and destination?
For a single source-destination pair, you may have thousands of intermediate points, that permute into millions of potential paths. No graph algorithm can iterate over this web efficiently.
1: Define the problem correctly.
The problem of finding an optimal route between two points using a precise algorithm like breath first search or Dijikstra is slow. To speed things up, we will resort to approximations.
One approximation that most people start with is Cartesian distance. This simplifies the problem as a distance optimization problem.
However, this won't work.
Figure 1. Me trying to get to the library when the new Game of Thrones book comes out.
Cartesian distance is a poor indicator of ETA in a road network. Not all points are connected in this topology (you cannot cross a park using your car).
So we must resort to using an approximate algorithm that works over a Network Topology: we must choose from the set of path-search algorithms.
2: Reduce the search space.
In the case of road networks, bigger is better. So we do the sensible thing: Choose wide streets.
This ensures you don't get stuck in unknown gulleys or off-beat roads. Wide streets are likely to be faster, have fewer traffic stops, and are less prone to dead-ends.
This technique of choosing a path on principle is called a heuristic, and the result of this action is called Pruning.
In the case of Google Maps, the pruning step is fulfilled by an algorithm called A-star search.
3: Reduce the size of the problem.
Every path could have thousands of intermediate points. Wide streets reduce the solution search space, but not the problem.
Go back to the idea of manually finding a route. If you need to learn how to get from a source to a destination, you will likely ask a friend!
"Hey, how do you get to 12th Baker Street, Marylebone, London?
"No."
"Do you know how to get to Marylebone, London?"
"Yes. Just take this right, followed by…."
Aha! The idea is to look for regions! We can reduce many points in our graph to hubs (points representing the entire region).
We then restrict our thinking to "Get to the centroid of the current region and then find the best path to the destination region".
And looking for hubs helps you reduce the number of intermediate points to manageable ones.
Figure 2. Me finally managing to get to the library.
This method of reducing points in a set is called Sieving. Sieving in Google Maps is performed by an algorithm called hub-partitioning.
These ideas may not yield optimal paths for every source-destination pair, but they significantly reduce the time to converge on an answer. Thinking as a customer, our requirements prioritize speed and safety of routes more than small optimizations on time to travel.
There are many more things to consider in the system design of Google Maps.
- Choosing the right database for Maps
- Finding nearby restaurants or stores
- Detecting traffic jams and updating routes
- Efficiently calculating an ETA
All of these are hard problems, but estimating a time of arrival for a massive network with millions of connected devices is a thing of itself.
The discussions around these problems are in our Google Maps chapter here.
Wrapping Up
The system design of Google Maps is a fusion of innovative graph technology with common-sense optimizations. Google Maps transforms webs of roads and intersections into a network of traversable connections to provide a seamless navigation experience.
.gif)
Figure 3. Google Maps System Design Diagram
Feel free to leave your thoughts and suggestions in the comments below. And if you liked the content, please register to get notifications for new articles.
Cheers!