The ETA Service

In one line: this lesson contains the course's cleanest example of a machine-learning component placed correctly — DeepETA predicts the residual rather than the answer, and understanding why is worth more than the whole architecture around it.

Two steps, and the second is the hard one

The two basic components of predicting an ETA given an origin and destination on a road network are:

• Calculate the shortest route from the origin to the destination.
• Compute the time required to travel the route.

The whole road network is represented as a graph. Intersections are represented by nodes, while edges represent road segments. The graph also depicts one-way streets, turn limitations, and speed limits.

Here the graph is real, and Dijkstra is the right thing to reject

The Yelp chapter mentioned Dijkstra and it was a carryover error — there was no graph, only a point set, and distance was a closed-form haversine calculation.

Here there is a graph. Intersections are vertices, roads are weighted edges, and finding a route genuinely is a shortest-path problem. So the design is right to invoke Dijkstra, and right about what follows:

To identify the shortest path, we can utilize routing algorithms such as Dijkstra's algorithm. However, Dijkstra, or any other algorithm that operates on top of an unprocessed graph, is quite slow for such a system. Therefore, this method is impractical at the scale at which these ride-hailing platforms operate.

Note the precise phrasing: "any algorithm that operates on top of an unprocessed graph." The problem is not the algorithm — it is running any algorithm over a raw graph of billions of vertices inside a request.

That is exactly that building block's conclusion, and the resolution is the same in kind: preprocess. What differs is the technique, and it is a genuinely better one.

Contraction hierarchies

To resolve these issues, we can split the whole graph into partitions. We preprocess the optimal path within partitions using contraction hierarchies and handle only the partition boundaries. This reduces query latency by partitioning the graph into smaller, mostly independent cells. The preprocessing stage can be executed in parallel across partitions.

What contraction hierarchies actually do, and why it beats that building block's approach

The design names the technique without explaining it, and the idea is elegant enough to be worth a paragraph.

Contraction means removing a vertex from the graph and, wherever removing it would have broken a shortest path, adding a shortcut edge that preserves the distance:

Before:  A --3--> B --4--> C     (B is a minor intersection)
Contract B:
After:   A -------7-------> C    (shortcut, weight 7)

Do this for every vertex, in order of increasing importance — residential turnings first, motorway junctions last — and you build a hierarchy. A query then searches upward from both endpoints through progressively more important roads and meets in the middle, never touching the vast majority of minor streets.

That mirrors how people actually navigate: get to a main road, take the motorway, exit near the destination, navigate local streets. The hierarchy encodes that intuition as a preprocessing step.

Compare that building block, which precomputed all-pairs shortest paths within a segment and connected segments via exit points. Contraction hierarchies are strictly better for this problem:

The last row matters: this is not an approximation. Contraction hierarchies return the true shortest path, they just avoid looking at most of the graph to find it.

The third row matters more for this chapter. Traffic changes constantly, and O(V²) recomputation per segment does not survive that. Choose the preprocessing technique by how expensive it is to repair, not only by how fast it queries.

The parallelism claim needs a caveat

For example, if each partition requires approximately one second to compute its segment, the overall response time approaches one second, assuming balanced workloads and minimal coordination overhead.

This is true and the caveats are load-bearing.

Balanced workloads. Partitions are not equal — a dense urban cell has orders of magnitude more vertices than a rural one. Unless partitions are sized by graph content rather than area, the slowest dominates. That is exactly the lesson that building block learned about static segments, applied to graph partitioning.

Minimal coordination. The partitions are not independent: a route crossing five cells needs their boundary connections stitched together, and the stitching is sequential.

One second is an eternity. ETA appears on the rider's screen while they wait, and during the rejection loop from Lesson 4 it is inside a latency budget already stretched thin. A one-second route computation per matching attempt is not viable — which is a strong argument for caching ETAs between frequently-paired regions rather than computing each fresh.

Fan-out latency is the maximum, not the average, and the maximum is set by the largest partition. That is the same tail-latency argument the Distributed Search and Maps chapters made.

Traffic as edge weights

Once we determine the best route, we calculate the expected travel time along the road segment, accounting for traffic. The traffic data will be the edge weights between the nodes.

This is that building block's dual-weight problem, and it is worse here

The Google Maps chapter established the tension precisely: you cannot precompute against weights that change constantly, so keep stable base weights for precomputation and overlay transitory conditions at query time.

Contraction hierarchies make that tension sharper, because the shortcuts themselves encode weights. Change an edge's weight and every shortcut that bypassed it may now be wrong.

The standard resolution is customizable route planning: separate the preprocessing into a topology phase, which depends only on the road network and changes almost never, and a weights phase, which is cheap to redo when traffic shifts. The expensive structural work is done once; the cheap customization runs every few minutes.

Same principle, one level deeper: separate what changes slowly from what changes quickly, and pay full price only for the slow part. The Maps chapter separated base from transitory weights; here you separate graph structure from weights entirely.

DeepETA

We use a machine learning component, DeepETA, to deliver an immediate improvement in metrics in production.

We use a routing engine that uses real-time traffic information and map data to predict an ETA and select the best path. We use a post-processing ML model that considers spatial and temporal parameters — source and destination, time of request, real-time traffic — to forecast the ETA residual.

Predicting the residual rather than the answer is the best idea in the chapter

Read that phrase again: the model forecasts the ETA residual — the error of the routing engine, not the ETA itself.

That is a substantially better design than replacing the router with a model, for four reasons.

The physics is already right. Distance divided by speed, along a known route, with known limits, gets most of the way there. Asking a neural network to relearn arithmetic from data is wasteful and worse.

The residual is where the learnable structure lives. The router cannot know that a particular junction backs up at 5 p.m., that a stadium empties on Saturdays, or that a pickup at an airport terminal always takes four extra minutes to reach the kerb. Those are systematic, repeating errors — exactly what a model learns well.

Failure degrades gracefully. If the model is unavailable, you ship the routing engine's ETA. Slightly worse, still correct. A model that produced the ETA outright has no fallback.

It is auditable. You can measure the residual model's contribution directly — does adding it reduce error? A monolithic model gives you no such decomposition.

The general form is worth carrying beyond ETAs: use a model to correct a principled baseline rather than to replace it. The baseline supplies structure, correctness, and a fallback; the model supplies the pattern the baseline cannot express.

It is the same instinct as that building block's transitory-weight overlay — a cheap correction layer on top of an expensive stable computation — and the same instinct as boosting. Model the error, not the outcome.

Two ETAs, two audiences, and the design conflates them

The API in Lesson 5 exposes showETA with an optional destination, which quietly reveals two different predictions:

The pickup ETA is the one Lesson 7 argued should drive matching, and it is short-horizon, so current traffic dominates.

The trip ETA is long-horizon, so it needs prediction rather than observation — traffic 30 minutes from now on a road you have not reached. That is that building block's historical-patterns argument, and it is a harder problem.

And the trip ETA feeds the fare estimate, which makes it financially consequential in a way the pickup ETA is not. Underestimate and riders feel overcharged; overestimate and they choose a competitor.

One service name, two prediction problems with different horizons and different consequences. Worth separating when you present it.

Interview signal by level

Next: where all this data lives.