Challenges of Google Maps' Design

Use graph partitions and precomputed paths to reduce routing work while preserving valid routes. Then separate relatively stable road topology from changing travel-time estimates.

Meeting the challenges

We previously identified two main challenges in the Introduction: scalability and ETA computation. This lesson explores solutions for both.

Scalability

A large road network can make unoptimized per-request search expensive. The target is to reduce visited vertices and cross-server requests without discarding roads that could belong to the chosen route.

Partition the road graph into smaller subgraphs called segments. Segments can be stored and processed independently for some work, but a cross-segment route still needs coordination and correct connections between boundaries. Partitioning alone does not establish a query-latency bound.

Segment

A segment is a partition of the map chosen to keep its graph manageable. In this hypothetical example, a city is divided into squares measuring $5\times 5$ miles. Actual memory use depends on road density, so equal geographic areas need not contain equally sized graphs.

Note: While we assume square segments for simplicity, segments can be arbitrary polygons.