Design the traffic prediction system behind Google Maps’ ETA and route recommendations. The system must forecast road speeds and congestion on every segment of a global road network, minutes to hours ahead, so that routing can pick the fastest path and display accurate arrival times.
It must fuse real-time probe data from millions of phones and fleet vehicles, historical patterns, live incidents (accidents, construction, events), and weather. It also has to respect the spatial and temporal dependencies that make a jam on one freeway cascade onto adjacent arterials minutes later.
How would you design this system? Cover the data ingestion and map-matching pipeline, the spatio-temporal forecasting model, how real-time and historical signals are combined, how incidents and events are incorporated, and how the ETA is computed and kept honest as conditions change.
The Problem: a jam does not stay on one road and probe coverage is uneven, yet the product must commit to a single arrival time for every trip, everywhere, right now.
Answer
The design is a streaming pipeline that turns anonymized probe traces into per-segment speed observations, then a spatio-temporal graph neural network over the road network that predicts a multi-horizon quantile speed distribution for every segment. Predictions are precomputed into a distributed speed store, and the routing engine reads them as time-dependent edge weights, so a route query never waits on a model call. Two decisions are pivotal. First, the model operates on supersegments (chains of consecutive segments that share traffic) rather than isolated edges, which fixes probe sparsity and lets message passing carry a jam upstream and onto parallel arterials. Second, the real-time signal is a residual on top of a historical speed profile, not a replacement for it, so accuracy degrades gracefully as probe density drops and as the horizon grows. Google’s published version of this system reports ETA accuracy improvements of up to 50% in several metros after moving from segment-local models to a GNN over supersegments.
(1) Map Matching And Aggregation: HMM map matching snaps noisy GPS traces to road segments, and traversals are aggregated into short time bins per segment and supersegment so no individual trip is recoverable.
(2) Historical Prior Plus Live Residual: a per-segment, per-time-of-week speed profile is the baseline; the live signal predicts the deviation from it, which is what makes sparse-probe roads survivable.
(3) Spatio-Temporal GNN: nodes are segments with live, historical, and static features; two to three rounds of message passing propagate congestion along the network, and multi-horizon heads emit speeds at 2, 10, 30, and 60 minutes.
(4) Incidents As Features Plus A Short-Horizon Override: accidents, closures, events, and weather enter as node and context features, with a corroborated override path that patches the next few minutes faster than the model can retrain.
(5) Precompute And Serve: predictions land in a segment-by-horizon key-value store read in single-digit milliseconds; routing runs time-dependent search so long trips use future speeds, not present ones.
(6) Quantile ETA And Mid-Trip Correction: the product shows a calibrated interval rather than a point estimate, and the ETA is re-estimated during the trip as the vehicle’s own trace becomes evidence.
Figure 1: The serving path: probes become segment observations, the model writes future speeds ahead of time, and the router only reads. Realized travel times close the loop as training labels.
Clarify Before Designing:
(1) Coverage And Probe Density: which markets, and what fraction of segments see enough probes in a five-minute window to support a live estimate at all?
(2) Horizon And Refresh: do we only serve depart-now ETAs, or also scheduled departures hours ahead, and how often must each segment be refreshed?
(3) Latency Budget: what is the end-to-end budget for a route query, and is the prediction allowed to run inline or must it be precomputed?
(4) Error Asymmetry: is arriving late worse than arriving early, and by how much, since that decides which quantile we display?
(5) Privacy Constraints: what aggregation thresholds and retention limits apply to location traces, and do they differ by region?
(6) Routing Ownership: do we control the routing engine (so we can change edge weights and spread traffic) or only publish speeds to a consumer?
Leave a Reply