How Uber Predicts the Future (Literally)

How Uber Computes ETA at Half a Million Requests per Second

The Problem

Imagine it’s September 2014 in Prague. You have a meeting in 15 minutes. You call a taxi, but the traffic is terrible. You arrive late, frustrated, and angry.

Then, you hear about this new app called Uber. You install it, type in your destination, and—bam—the app tells you exactly when the driver will arrive.

How does it know?

The answer isn't magic; it's math. Specifically, it’s a system designed to handle half a million requests per second.

The 4 Scenarios

Before we get into the math, we need to understand when Uber is calculating this.

1. Eyeball: You type "Home" into the app.
2. Dispatch: Uber is looking for a driver nearby.
3. Pick up: The driver is on their way to you.
4. On-trip: You are in the car, and Uber is telling you when you’ll arrive.

That’s a lot of math happening in the background for every single ride.

The Challenge: It’s Not a Straight Line

If you want to get from point A to point B, you might assume it’s a straight line. But real life is messy. It’s a maze of one-way streets, highways, and traffic lights.

To solve this, Uber treats the map like a giant Graph.

• Nodes: Every intersection (stop sign, traffic light, fork in the road).
• Edges: The road connecting those intersections.

[Visual 1: The Graph Concept]

[Node A]
/ \
[Node B] ---> [Node C]
\ /
[Node D]

Computing an ETA becomes a puzzle: Which path from A to D is the fastest?

The Bottleneck: Dijkstra’s Algorithm

The standard way to solve this puzzle is called Dijkstra’s Algorithm. It’s great for small maps, but terrible for big ones.

In the San Francisco Bay Area alone, there are 500,000 intersections. Dijkstra’s algorithm would have to check every single one of them to find the best route. That’s too slow for Uber.

The Solution: The "Circle" Trick

Uber engineers didn't just use Dijkstra; they used a technique called Contraction Hierarchies combined with Partitioning.

Here is the visual explanation of how it works:

[Visual 2: The Area vs. The Perimeter]

Imagine the map is a circle.

• The Old Way (Dijkstra): You have to search the entire area of the circle to find the best path.
• Complexity: $\pi \times r^2$ (Area)
• Result: Slow. You have to check 500,000 nodes.

• The Uber Way (Partitioning): They split the map into chunks. To find the best path, you only need to look at the edge of the circle (the boundary).
• Complexity: $2 \times \pi \times r$ (Perimeter)
• Result: Fast. You only check about 700 nodes.

By pre-computing shortcuts and only looking at the boundaries of map sections, Uber turns a massive calculation into a tiny one.

Layer 2: Traffic

Now that we have the route, we need to know how fast we can drive.

Uber treats traffic like "speed bumps" on the graph. They assign a weight to every road segment based on current traffic.

But traffic changes. So, Uber combines two things:

1. Real-time data: What is happening right now?
2. Historical data: What usually happens at this time of day?

This creates a super-accurate prediction of travel time.

Layer 3: Map Matching (Fixing the GPS)

GPS signals are noisy. They can jump around, especially in cities with tall buildings (multipath effect) or inside tunnels.

[Visual 3: The Spaghetti GPS]

(Actual Road)
_________
/ \
/ \
/ \
/ \
(GPS Signal - Noisy!)

If Uber trusts the GPS signal, the ETA will be wrong. The car might be on the highway, but the GPS thinks it's on a side street.

Uber uses Map Matching to fix this. They use two algorithms:

1. Kalman Filter: It smooths out the jagged GPS line. It acts like a person guessing where you are based on your previous position.
2. Viterbi Algorithm: It looks at the "spaghetti" GPS line and tries to find the smoothest path that actually exists on the road network.

[Visual 4: The Fix]

(Actual Road)
_________
/ \
/ \
/ \
/ \
(GPS Signal - Noisy!)
|
v
(Smoothed Matched Path)

The Bottom Line

If Uber gives you a bad ETA, you don't trust the app. You cancel. You walk. You lose money.

With 18 million trips a day, a bad ETA costs Uber billions.

By combining Graph Partitioning, Traffic Data, and Map Matching, Uber manages to compute these predictions instantly, keeping millions of people on time and on the road.