Challenges in Google Maps System Design

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 humongous 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 large graph to find the shortest path. This results in an 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 (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 traversedTraversing is visiting the graph vertices to reach a specific vertex.. A city, for example, can be divided into hundreds of segments, each measuring $5 \times 5\ miles$.

A segment is not necessarily a square. Instead, it can be a polygon. But, we are assuming square segments for ease of explanation.

Each segment has four coordinates that help determine which segment the user is in. Each coordinate consists of two values, latitude and longitude. In a geopositioning coordinate system, the location or the position is a pair of latitude and longitude.