Segmentation: Partitioning the World

In one line: this is the answer to Lesson 2's algorithmic challenge, and the move is one you have seen before under other names — make the unit small enough to fit in memory, then do the expensive work in advance.

What a segment is

A segment is a manageable partition of the global map. Because a segment's road network is small, it can be easily loaded into memory, updated, and traversed. A city might be divided into hundreds of segments, each measuring 5×5 miles.

Note: while we assume square segments for simplicity, segments can be arbitrary polygons.

Each segment is defined by boundary coordinates (latitude and longitude) that help determine which segment a user is currently located in.

        Globe partitioned into segments

  +----------+----------+----------+
  | (lat,lon)|          |          |
  |    S1    |    S2    |    S3    |
  +----------+----------+----------+
  |          |          |          |
  |    S4    |    S5    |    S6    |
  +----------+----------+----------+

  Each segment: 4 boundary coordinates, ~5x5 miles

'Small enough to fit in memory' is the entire criterion — everything else follows

Lesson 2 diagnosed the problem precisely: the global graph "was too large to fit in memory, rendering query processing impossible." Once traversal hits disk, per-vertex cost rises by orders of magnitude and the 2–3 second budget is gone.

So the segment size is not chosen for elegance. It is chosen so that one segment's road network fits in one server's RAM.

Once that holds, three things become true at once:

• Traversal is fast — an in-memory graph of hundreds of vertices, not billions.
• Segments are independent — different servers can hold different segments, and Lesson 10 does exactly that.
• Queries parallelize — many segments can be processed simultaneously, which That is the same move as sharding a database or partitioning a search index: the unit of partitioning is chosen so the working set fits the machine. the inverted-index pattern partitioned documents so each node's index fit in RAM; this partitions geography for the same reason.

Geography is a natural partition key — and that is unusually convenient

Most systems have to invent a partition key and worry about skew. The Sharded Counters chapter agonized over shard selection; pub-sub warned that a bad partition key produces a hot partition.

Here the key is latitude and longitude, and it comes with a property most partition keys lack: queries are inherently local. A route from one part of a city to another touches nearby segments and nothing else. There is no equivalent of a query that needs data from everywhere.

It also makes routing to the right shard trivial — Lesson 10's key-value store maps segment boundaries to server IDs, and a coordinate resolves to a segment by simple comparison. No hash, no lookup table of arbitrary assignments.

The catch, which Lesson 12 raises: geography is not uniformly dense. A 5×5-mile square in Manhattan contains vastly more road network than one in the Nevada desert. Fixed-size segments therefore produce wildly uneven graphs — which is why Lesson 12 suggests non-uniform segment sizes, smaller in cities and larger in rural areas.

How the world actually gets indexed

Fixed lat/lon squares are the simplest partition and they are not what production systems use, for the reason Lesson 12 raises: geography is not uniformly dense. A 5×5-mile square in Manhattan holds thousands of intersections; the same square in rural Nevada holds a dozen.

Geohash interleaves latitude and longitude bits into a string, so a shared prefix means physical proximity and a range scan finds neighbours. Quadtrees subdivide a cell only when it exceeds a density threshold, which is exactly the fix for the Manhattan-versus-Nevada problem. S2 maps the sphere onto a space-filling curve, avoiding the distortion a flat lat/lon grid suffers near the poles.

This chapter keeps fixed squares because they make the routing argument clearest. In an interview, say that out loud and name what you would actually use: "I'm drawing a uniform grid for clarity, but I'd index with a quadtree so cell size follows road density, and the segment-to-server mapping falls out of the cell id."

The routing literature calls these precomputed partitions routing tiles, which is the same idea one level up: a tile is a segment plus its precomputed internal paths, versioned and shipped as a unit.

Finding paths within a segment

To find paths within a single segment, we treat the road network as a graph, with intersections as vertices and roads as edges. Edges carry weights representing distance, time, or traffic. Since multiple paths exist, we use Dijkstra's and A* to identify the optimal route.

Dijkstra was rejected globally and is fine locally — same algorithm, different scale

Lesson 2 said naive Dijkstra "is not sufficient at this scale." Here it is the recommended algorithm. That is not a contradiction — it is the point of segmentation.

Dijkstra's cost scales with the graph it runs on. On billions of vertices it is hopeless; on a segment holding hundreds, it is instant.

A* is the refinement worth knowing: it is Dijkstra plus a heuristic estimating remaining distance to the target, so it explores toward the destination rather than uniformly outward. For geographic routing the heuristic is natural — straight-line distance — which makes A* substantially faster than Dijkstra on road networks and is why both are named.

The transferable point: an algorithm's viability is a property of the input size, not of the algorithm. Making the input small enough is often better than finding a cleverer algorithm.

Precomputing paths

We pre-compute shortest paths within segments and store the results in a distributed storage system. This caching prevents redundant calculations for frequent queries. The stored data includes the shortest distance, the estimated travel time, and the sequence of vertices along the path.

This heavy processing occurs offline, ensuring it does not impact the user's critical path during a live query.

Cached output of the shortest path algorithm

Source | Destination | Distance (m) | ETA (min) | Path
-------|-------------|--------------|-----------|--------
   A   |      D      |      11      |    15     | A->C->D
   G   |      D      |      12      |    16.5   | G->C->D

Precomputation converts a compute problem into a lookup — the classic space-for-time trade

At query time, finding the path within a segment stops being a graph traversal and becomes a key lookup. That is what makes the 2–3 second budget achievable.

The trade is explicit:

• Storage cost — every source-destination pair within a segment, stored. That is O(V²) per segment in the worst case, which is exactly why segments must be small.
• Staleness — precomputed ETAs assume the traffic conditions at computation time, so Lesson 11 needs a graph preprocessing service to recompute after weights change.
• Offline compute — real work, just not on the user's critical path.

Note what is stored: distance, ETA, and the vertex sequence. The vertex sequence is what enables Lesson 4's turn-by-turn directions — you cannot give directions from a distance number alone.

And note the ETA is stored alongside the path, which is why Lesson 9's traffic updates must trigger recomputation: the distance stays valid, the ETA does not.

O(V²) per segment is why segment size is bounded from above as well as below

Lesson 12 notes segments must be small enough to fit in memory — a lower bound on how coarse they can be. Precomputation supplies an upper bound from the other direction.

Storing shortest paths between all pairs in a segment costs roughly V² entries. Double the segment size and you roughly quadruple the precomputation storage and time.

So segment size is squeezed from both sides:

• Too large → does not fit in memory, and all-pairs precomputation becomes prohibitive.
• Too small → more segments, so more cross-segment routing, which Lessons 7 and 8 show is the expensive path.

That is a genuine optimization with a real optimum, and it is the sort of parameter you would tune empirically. It also strengthens Lesson 12's argument for non-uniform sizing — dense urban areas want smaller segments to keep V manageable, sparse rural ones can be much larger.

Precomputation converts a compute problem into a lookup — the classic space-for-time trade. It also explains why segment size is bounded on both sides: too large and it will not fit in memory and the all-pairs precomputation becomes quadratically expensive.

Interview signal by level

Next: what happens when you do not start at an intersection.