Open a navigation app at 5:40 pm and it tells you the motorway is red, that the side street is faster, and that you will arrive at 6:12. Three different systems produced those three answers. A traffic pipeline turned millions of anonymous location reports into a speed for every road segment. A router searched a graph whose edge weights were those speeds. An ETA model predicted how the speeds on your route will change during the 32 minutes you will spend driving it. This article designs all three, from first principles, as a reference architecture.
A note on sources. Google has described parts of its system publicly: traffic is computed from aggregated, anonymised location data from people who opt in, combined with historical patterns; and in 2020 DeepMind and the Google Maps team described graph neural networks that predict travel time over supersegments, reporting ETA accuracy improvements of up to 50 percent in cities including Berlin, Jakarta, Sao Paulo, Sydney, Tokyo and Washington D.C. Internal component names, volumes and thresholds are not public, so the numbers below are design values you would choose and tune, not claims about Google. The driver-location write path and ETA as a dispatch cost are covered in designing Uber dispatch; this page owns the traffic layer underneath.
The problem in one picture
The input is a stream of noisy points: latitude, longitude, timestamp, accuracy estimate, sometimes heading and speed. The road network is a directed graph of segments, each a polyline between two junctions with a length, a speed limit, a road class and turn restrictions. The output is a function from (segment, time) to expected traversal seconds, refreshed every minute or so, plus a model that projects it forward. Everything in between is about two difficulties: points do not say which road they are on, and a single segment in a quiet suburb may see three phones in fifteen minutes, so the live signal is sparse exactly where it is hardest to guess.
Ingest: batching, privacy and partitioning
Phones batch fixes and upload them every 30 to 60 seconds to save battery, so the pipeline must accept late, out-of-order batches and judge freshness by fix time, not arrival time. The gateway authenticates, rate-limits per device, and drops fixes with poor reported accuracy.
Privacy is an architecture decision, not a policy footnote. A design that holds up keeps only a rotating pseudonymous trace id (rotated often so traces cannot be stitched into a life), trims the first and last few hundred metres of each trace so homes and workplaces do not appear, and never publishes a segment speed computed from fewer than k distinct traces. Raw traces live for hours, not months; only aggregates persist.
After the privacy layer, fixes go to a partitioned log keyed by map tile (an S2 cell or a geohash prefix at roughly city-district size). Keying by tile keeps every trace that touches a district on one partition, so matching and aggregation are local. Hot tiles (a city centre at rush hour) are split to a finer level; the mechanics are the same as any hot-key problem, see Kafka partition architecture.
Map matching: which road was the phone on
A fix 8 metres from a motorway and 11 metres from the parallel service road is ambiguous on its own. Across a sequence it is not: a car cannot jump from the service road to the motorway between two fixes 3 seconds apart without a ramp. The standard technique is a hidden Markov model. Hidden states are candidate segments near each fix. The emission probability says how likely the fix is given the true position on a segment (a Gaussian in distance). The transition probability says how plausible it is to move between two candidates, by comparing the road-network distance between them with the straight-line distance between the fixes. Viterbi then finds the most likely segment sequence.
import math
SIGMA_GPS = 6.0 # metres, GPS noise; tune from fixes on known roads
BETA = 4.0 # metres, tolerance for route-vs-straight-line mismatch
def emission(dist_to_segment_m):
# Probability that a fix this far from a segment was really on it.
return -0.5 * (dist_to_segment_m / SIGMA_GPS) ** 2
def transition(route_m, straight_m):
# Penalise candidate pairs whose road distance differs from the crow-fly distance.
return -abs(route_m - straight_m) / BETA
def viterbi(fixes, candidates, road_distance):
# candidates[i]: list of (segment_id, dist_m, snapped_point); haversine() not shown
score = {c[0]: emission(c[1]) for c in candidates[0]}
back = [{}]
for i in range(1, len(fixes)):
straight = haversine(fixes[i - 1], fixes[i])
new_score, ptr = {}, {}
for seg, dist, point in candidates[i]:
best, arg = -math.inf, None
for prev_seg, _, prev_point in candidates[i - 1]:
r = road_distance(prev_point, point) # bounded Dijkstra, returns inf if unreachable
if r == math.inf:
continue
s = score.get(prev_seg, -math.inf) + transition(r, straight)
if s > best:
best, arg = s, prev_seg
if arg is not None:
new_score[seg] = best + emission(dist)
ptr[seg] = arg
if not new_score: # HMM break: tunnel, GPS jump, missing road
return None # caller splits the trace and matches the halves
score, back = new_score, back + [ptr]
seg = max(score, key=score.get)
path = [seg]
for ptr in reversed(back[1:]):
seg = ptr[seg]
path.append(seg)
return list(reversed(path))Two engineering points matter more than the maths. First, road_distance is a bounded shortest-path search per candidate pair, which dominates cost; cap candidates at the four or five nearest segments within a radius, and cache searches within a trace. Second, HMM breaks are normal (tunnels, urban canyons, a road missing from the map). Split the trace and match the pieces; a stream of breaks in one place is itself a signal that the map is wrong there and should go to the map-edit queue.
Matching runs online with a short lag, emitting a traversal (segment id, entry time, exit time, interpolated at the junctions) once the path behind a sliding window is fixed.
Estimating speed per segment
Each traversal gives one observed speed. The estimator for a segment over the last window (for example 5 minutes for a motorway, 15 for a residential street) must survive outliers: the bus that stopped at every stop, the courier who parked, the cyclist matched to a road. Use the median or a trimmed mean, not the mean, and treat vehicles as different classes when the data allows. Then blend with history, weighting the live value by how much evidence there is.
from statistics import median
MIN_PROBES = 3 # below this the live signal is noise
TAU = 6 # probes at which live and history get equal weight
def segment_speed(traversals, historical_kmh, length_m, free_flow_kmh):
"""traversals: list of (entry_ts, exit_ts) for one segment in the last window."""
speeds = []
for t_in, t_out in traversals:
secs = t_out - t_in
if secs <= 0:
continue
kmh = (length_m / secs) * 3.6
if kmh > 1.5 * free_flow_kmh: # matching error or clock skew
continue
speeds.append(kmh)
n = len(speeds)
if n < MIN_PROBES:
return historical_kmh, 0.0
live = median(speeds) # robust to the one delivery van that stopped
w = n / (n + TAU) # confidence grows with sample size
return w * live + (1 - w) * historical_kmh, wHistorical profiles are the slow path. For each segment, compute typical speed per weekday and 15-minute slot over the last several weeks, with separate profiles for public holidays and school terms. This prior is what makes a quiet street usable: with zero live probes it returns the Tuesday-at-17:45 value instead of the speed limit. It also gives you anomaly detection for free: a segment where live speed is far below history with high confidence is a candidate incident.
From speeds to ETAs: why supersegments
Summing current segment times along a route gives a now-cast: the time the trip would take if traffic froze. For a 30-minute trip that is wrong in a predictable way, because the queue you reach in 20 minutes will have grown or cleared. Predicting it needs context from neighbouring roads: congestion propagates backwards from a bottleneck, and a jam on an on-ramp predicts one on the motorway.
The approach DeepMind described groups adjacent segments that share significant traffic volume into supersegments, and runs a graph neural network over the local road graph: nodes are segments, edges connect consecutive segments and segments joined at intersections, and message passing lets each segment's prediction see its neighbours' recent speeds. Each supersegment gets its own travel-time prediction. They also reported that training was unstable across the varied supersegment graphs and used MetaGradients to adapt the learning rate during training, which is a reminder that the hard part of production ML here is robustness across thousands of different subgraphs, not peak accuracy on one.
In a reference design, the ETA service splits the chosen path into supersegments, batches their features and sums the predicted seconds. Keep the summed now-cast as a fallback when the model is unavailable or a supersegment is new.
Routing on live weights
Plain Dijkstra on a continental graph is far too slow per request. Contraction hierarchies add shortcut edges so a query touches only a few thousand nodes, but classic ones bake weights into the shortcuts. Customizable variants split a metric-independent preprocessing step (node order and shortcut topology, once per map version) from a customization step that recomputes shortcut weights in seconds. Live traffic becomes a new metric every minute, swapped in atomically.
Route choice and ETA are separate calls: the router finds a few good paths on a cheap metric (live weights near the origin, profile weights further out), and the ETA model prices them precisely. That keeps the expensive model out of the search loop.
Incidents and the feedback loop
Incidents come from three places: user reports, authority feeds, and inference (a sharp, confident drop below history on consecutive segments). Inferred closures are the dangerous ones. If you mark a road closed, routing sends nobody down it, so no probes arrive to tell you it reopened. Give every inferred closure a decay timer, keep routing a small fraction of traffic or rely on other signals to re-verify, and treat zero probes on a closed road as unknown, not as confirmation.
The same loop shapes normal traffic. When the app routes thousands of drivers off a jammed motorway onto one side street, the side street jams. Systems damp this with route diversity (spreading near-equal alternatives across users) and by including predicted load in the weights. Load shedding for the request path itself follows the usual patterns in load shedding.
Worked example: a Tuesday evening queue
Segment S is a 600 m stretch of urban arterial, free flow 50 km/h, historical Tuesday 17:45 speed 28 km/h. In the last 10-minute window the matcher emitted seven traversals with speeds 12, 11, 14, 9, 13, 41 and 12 km/h. The 41 is a motorbike filtering through traffic. Median is 12 km/h; the mean would be 16. With n = 7 and TAU = 6, the live weight is 7/13, about 0.54, so the blended estimate is 0.54 x 12 + 0.46 x 28, about 19.4 km/h, giving a traversal time near 111 seconds against a historical 77.
Live speed is under half of history, and the downstream segments agree while the upstream one is starting to slow: a queue growing back from a bottleneck. The new metric is published within a minute, and for a driver five kilometres away the ETA model predicts S will be slower still when they arrive, so the router offers a parallel road now, before the driver is in the queue.
Failure modes
- Sparse probes at night or in rural areas. The live weight falls toward zero and the profile carries the answer; that is correct, but alert when a major road's probe count drops sharply, because it usually means an ingest or matching fault, not empty roads.
- Matching onto the wrong carriageway. A parallel frontage road gets motorway speeds or the reverse. Use heading, turn restrictions and transition penalties, and audit segments whose speed distribution is bimodal.
- Spoofed or synthetic probes. A small number of devices reporting slow movement can fake a jam on a quiet street. Require k distinct traces per segment, weight by device reputation, and cap any single trace's influence.
- Stale metric. If customization falls behind, routes use old weights while ETAs look current. Publish the metric's timestamp with every route and fall back to profiles beyond a staleness bound.
- Regional partition loss. Losing the tiles for one city should degrade that city to historical weights, not fail routes. Geographic sharding and failover are discussed in geo-distributed systems.
Trade-offs to decide explicitly
| Decision | Lean one way | Lean the other |
|---|---|---|
| Window length | Short: reacts in minutes, noisy | Long: stable, lags incidents |
| Privacy threshold k | High: safer, more segments fall back to history | Low: more coverage, more re-identification risk |
| Routing metric | Live everywhere: simple, wrong for long trips | Time-dependent: accurate, costly customization |
| ETA model | Sum of segment now-casts: cheap, explainable | Graph model: better on long trips, needs fallback |
| Incident inference | Aggressive: early warnings, false closures | Conservative: fewer errors, slower reroutes |
What to do next
- Pick a tile scheme and partition the probe log by tile; measure the hottest partition at peak.
- Implement HMM matching on a few hundred real traces and hand-check breaks before scaling.
- Build weekday-by-15-minute historical profiles first; they are the fallback for everything else.
- Add the live estimator with a median, a minimum probe count and confidence blending; plot live against history per segment.
- Measure ETA error by trip length; only add a learned ETA model where the now-cast error grows with distance.
- Give inferred closures a decay timer and alert on probe-count collapses for major roads.
- Cache route responses carefully: key by origin and destination cells and metric version, as in caching strategies.