EP02 - Google Maps

How Google Maps predicts traffic before you leave. Learn about location probing, Graph Neural Networks (GNNs), S2 Geometry, Hilbert Curves, and Contraction Hierarchies for routing.

Tweet coming soon

How... how does it know traffic is 'heavier'?

I haven't even left the driveway yet. Is there a satellite watching my street?

Satellites are too slow. They update once a day. Traffic changes every second.

Kurumi! Then how? Is it cameras? Is it the CIA birds spying me on every corner?

Cameras?

You are the camera. You, and the millions of other drivers.

Me? How?

Google Maps has over 1 billion monthly active users.

Every Android phone, every iPhone with Maps open... they are all sending little pings.

You aren't a person to them. You are a **Probe**.

That... sounds invasive.

It's anonymized. But yes. You're crowd-sourcing your own traffic report.

Okay, so it knows current traffic. But it says '28 minutes'. That's a prediction for the *future*.

How does it know what traffic will be like in 15 minutes when I reach the highway?

Ah. Instead of measuring speed, we decide to predict human behavior.

To predict the future, Google use the ghosts of the past.

They store historical speed data for every road segment on Earth.

Every road?

Every sampled meter. For years.

They know that on Tuesdays at 8:45 AM, this specific on-ramp slows down to 20mph.

Okay, but today is worse. Why?

Because the **Graph Neural Network (GNN)** saw a pattern.

A neural network? Like ChatGPT?

No. A **Graph** network. Think of the city not as a picture, but as a web of connected nodes.

Road A connects to Road B. Road B connects to Road C.

If an accident happens on Road A, the cars don't disappear.

They spill over.

The GNN simulates this 'Shockwave'. It knows that a blockage here causes a slowdown 5 miles away in 10 minutes.

So it's simulating the domino effect?

Exactly. AKA **'Supersegments'**. It groups chunks of roads together to predict how they infect each other.

That sounds like a lot of data. Millions of roads. How does the phone search it so fast?

If I zoom out, it renders the whole world instantly.

Because the map isn't stored as a picture. It's stored as a **Fractal**.

A fractal?

Drive. We're late. I'll explain **S2 Geometry**.

Computers hate spheres. The math is messy. There's singularities at the poles.

So Google projects the Earth onto a Cube.

Each face is a Quad-tree. This way you can recursively divide it into smaller and smaller cells.

Level 0 is massive. Level 30 is the size of a coin.

Now, the genius part. How do you store a 2D map in a 1D database?

You can't? It's 2D.

You can. Check out **Hilbert Curve**.

It's a space-filling curve. It visits every cell exactly once.

It turns a coordinate (Latitude, Longitude) into a single long Integer.

Why does turning it into a line help?

Because computers are great at sorting numbers.

If two numbers are close on the curve, they are close on the map.

To find 'coffee shops near me', the database doesn't scan the whole world. It just scans a tiny range of numbers on the curve.

Okay, so S2 cells organize the map. GNNs predict the traffic.

But how does it find the *best* path? There must be a million ways to get to my office.

More than a million. If you used brute force, your phone would melt.

They use **Contraction Hierarchies**.

Imagine calculating every turn on every tiny street between here and Tokyo.

Useless. You don't need to know the residential streets in Osaka.

They pre-calculate 'Shortcuts'. They know that to leave this neighborhood, you *must* pass through one of three exits.

They 'contract' the graph. They ignore the small roads in the middle and only look at the entry/exit points.

It turns a graph of 1 billion nodes into a few thousand important ones.

It's amazing how it does all this in milliseconds.

It has to. Google Maps handle **millions of requests per minute**.

But there's a flaw.

A flaw?

The system assumes rational actors.

It assumes people follow the speed limit, or the flow of traffic.

It also assumes the data is real.

What do you mean?

Have you heard of the '99 Phone Hack'?

An artist put 99 phones in a wagon and walked slowly down an empty street.

Google saw 99 'cars' moving at walking speed. It thought there was a massive traffic jam.

It rerouted real drivers away from a completely empty street.

So a wagon could trick the algorithm.

It proves the system doesn't know *reality*. It only knows *data*.

To the algorithm, data is truth. Even when it's a lie.

You know, the probing, the tracking, the prediction. How's that different from getting watched by CIA?

Do you want to be tracked or be late?

Don't ask stupid questions and hurry up.