Predictive Systems
Google Maps ETA Prediction
How traffic, road conditions and years of historical data combine into a single number: the minute you will arrive.
How traffic, road conditions and years of historical data combine into a single number: the minute you will arrive.
You type a destination and, before you have put the phone down, a number appears: 34 minutes. That number is a prediction about the future of a city — thousands of vehicles, hundreds of traffic signals and a road network you will only partly use.
The hard part is not measuring distance. Distance is trivial. The hard part is that the same stretch of road takes four minutes at 11am and nineteen minutes at 6pm, and the system has to know which of those you are about to experience.
So an ETA is really two predictions stitched together: how long each individual piece of road will take, and which pieces of road you will actually drive on.
Think of it like this: it is less like measuring a piece of string and more like forecasting weather along a specific path — using what is happening right now, plus what usually happens at this hour on this day.
An ETA has to satisfy several demands that pull against each other:
Being ten minutes wrong on a thirty-minute trip destroys trust in the whole product.
The route and its estimate must be computed in well under a second, before the user notices any wait.
It has to work on a motorway with rich data and on a village road with almost none.
An accident two minutes ago should already be reflected in the number you are shown.
An estimate that jumps around every few seconds feels broken, even when each individual value is defensible.
The system is a pipeline: the map is stored as a graph, live and historical speed data continuously annotate that graph, and a routing engine searches it to produce both a path and a time.
The map is stored as a graph: intersections are nodes, and the stretches of road between them are edges carrying attributes like length, speed limit and road class.
In shortThe map is turned into a giant join-the-dots network, where each line between dots is one piece of road.
Anonymised, aggregated location signals from phones and vehicles currently in traffic reveal how fast each road segment is actually moving right now.
In shortEveryone already driving is unknowingly acting as a traffic sensor for everyone about to drive.
For every segment, the system stores typical speeds by time of day and day of week, built from years of observations.
In shortIt remembers that this road is always slow at 9am on a Tuesday, even before today's traffic shows up.
A learned model predicts how long a specific segment will take, combining live speed, historical profile, road class, weather and the time you will actually arrive at that segment.
In shortFor each piece of road it asks: given everything we know, how long will this bit take you?
Searches the weighted graph for the best path, where edge weights are predicted travel times rather than raw distances.
In shortIt finds the quickest way through, not the shortest way through, and those are often different.
As you drive, your own position updates the remaining route and the estimate is recomputed against the latest conditions.
In shortThe number keeps quietly correcting itself as reality unfolds.
Your raw GPS coordinate is matched to the nearest plausible road segment, since satellite positions are rarely exactly on the tarmac.
In shortIt works out which road you are actually on, not just roughly where you are.
The routing engine generates several plausible paths to the destination rather than committing to one immediately.
In shortIt sketches a few different ways of getting there before picking.
Each segment on each candidate route is given a predicted traversal time from the model, using live and historical inputs.
In shortEvery individual piece of road gets its own little time estimate.
For segments far along the route, the system predicts conditions at the time you will reach them, not conditions now.
In shortIt guesses what that junction will be like in twenty minutes, because that is when you will get there.
Segment times are summed, then adjusted for turns, signals, junction delays and historical bias corrections.
In shortIt adds it all up, then adds a bit more for turning, waiting and real-world friction.
Once you are moving, your actual progress is compared against the prediction and the remaining estimate is revised.
In shortIt keeps score of how it is doing and quietly nudges the number as you go.
Before any prediction is possible, the physical world has to become a data structure the machine can search efficiently.
Intersections become nodes; the road between two intersections becomes a directed edge, with separate edges for each direction of travel.
In shortJunctions are dots, roads are arrows between them, and one-way streets only get an arrow one way.
The weight of an edge is not its length but its predicted travel time, which is why the chosen route is sometimes longer in kilometres.
In shortRoads are measured in minutes, not metres, which is why the long way round sometimes wins.
Crossing oncoming traffic, waiting at a signal or making a difficult turn carry their own costs, modelled separately from the roads themselves.
In shortTurning right across traffic genuinely costs time, and the model knows it.
Techniques such as contraction hierarchies precompute long-distance shortcuts so cross-country routes do not require searching every small road.
In shortMotorway-scale routes are worked out in advance, so it never has to consider every side street.
The obvious method is distance divided by speed limit. It is fast, easy and wrong in exactly the situations that matter most:
In short: the system does not calculate how long the road is. It predicts how long each piece of it will take you, at the moment you will be on it, and adds those predictions up.
A shifting ETA looks like the system being unsure. It is usually the system being honest as new information arrives.
An incident, a signal failure or a sudden surge in volume on a segment ahead updates that segment's live speed, and therefore your remaining estimate.
In shortSomething happened up ahead after you set off, and the number reflects it.
Predicting a segment thirty minutes out is inherently less certain than predicting it two minutes out; as you approach, the guess is replaced by near-observation.
In shortThe closer you get, the less it has to guess, so the number gets sharper.
Missing a turn or choosing a different lane triggers a re-route, which is a fresh set of segments and therefore a fresh estimate.
In shortYou went a different way, so it started the sum again.
If you are consistently travelling faster or slower than predicted, the system can apply a correction to the remainder of the trip.
In shortIf you are running ahead of its guess, it assumes you will keep doing so.
Serving billions of routing requests over a planet-sized graph requires the work to be spread out and heavily precomputed:
| Layer | Common Choices |
|---|---|
| Map Data Store | Partitioned road-graph storage with versioned map releases |
| Probe Ingestion | High-throughput streaming pipelines (Kafka-class) for anonymised location signals |
| Traffic Aggregation | Stream processing to roll raw probes into per-segment live speeds |
| Historical Store | Time-series speed profiles keyed by segment, hour and day of week |
| Prediction Model | Learned travel-time models, increasingly graph neural networks over road networks |
| Routing Engine | Contraction hierarchies or similar precomputed shortest-path structures |
| Serving Layer | In-memory caches for hot routes and frequently requested corridors |
ETA prediction looks like arithmetic and is actually forecasting. It is a strong template for any system that must commit to a confident number about the future while continuously revising it as reality arrives — which is most operational promises a business makes to a customer.
A quick, no-nonsense translation of the technical terms used above.
One stretch of road between two junctions, treated as a single unit for measurement and prediction.
The cost of travelling along a segment. Here it is predicted minutes, not distance.
Matching an imprecise GPS coordinate to the road you are most likely actually on.
Anonymised, aggregated location signals from devices already in traffic, used as live speed sensors.
The typical speed of a segment at a given hour and day, learned from long-run observation.
A precomputation technique that adds long-distance shortcuts to the graph so routing does not need to examine every small road.
How far into the future a prediction reaches. Longer horizons are inherently less certain.
Predicting conditions on a segment for the moment you will reach it, rather than for right now.