Challenges of Google Maps' Design
Let's understand and resolve the key challenges in designing a system like Google Maps.
We'll cover the following...
Meeting the challenges
We listed two challenges in the Introduction lesson: scalability and ETA computation. Let’s see how we meet these challenges.
Scalability
Scalability is about the ability to efficiently process a huge road network graph. We have a graph with billions of vertices and edges, and the key challenges are inefficient loading, updating, and performing computations. For example, we have to traverse the whole graph to find the shortest path. This results in increased query time for the user. So, what could be the solution to this problem?
The idea is to break down a large graph into smaller subgraphs, or partitions. The subgraphs can be processed and queried in parallel. As a result, the graph construction and query processing time will be greatly decreased. So, we divide the globe into small parts called segments. Each segment corresponds to a subgraph.
Segment
A segment is a small area on which we can work easily. Finding paths within these segments works because the segment’s road network graph is small and can be loaded easily in the main memory, updated, and