Google Maps Routing, Traffic and Tiles.

How Do You Find the Fastest Way Through a Billion Road Segments, While the Roads Keep Changing Speed Under You?

It is 5:40 pm in Bengaluru. Ananya has a flight at 8:30 from Kempegowda International Airport, 38 km north of her flat in Koramangala. She opens the map app and types "airport". In a fifth of a second she sees three routes: one over the Hebbal flyover, one along the Outer Ring Road through Hennur, and a longer one on the toll road. The first says 1 hr 12 min.

She leaves at 5:45. At 6:02 a truck breaks down on the Outer Ring Road, a few kilometres ahead of the cars that took the second route. Ananya isn't on it, but the app has to know within a couple of minutes, from nothing but the phones crawling past the truck, and send everyone behind them another way. And the 1 hr 12 min it promised at 5:40 had to account for the Hebbal jam that only forms at 6:15, when she would get there.

This is the system we'll design today.

The Interview Begins#

You're interviewing at a company building a navigation app. The interviewer opens a map on the screen, drags it across a city, zooms into a junction, then types two addresses. Three coloured lines appear, each with a time. One of the roads on the map is red.

Your Questions#

Functional Requirements#

Non-Functional Requirements#

Traffic Estimation#

Routing Compute Estimation#

Storage Estimation#

Tile Estimation#

Key Metrics Summary#

System Architecture#

%% title: Routing, traffic and tiles architecture
flowchart TD
  subgraph L1["Layer 1 · Clients"]
    direction LR
    AND@{ icon: "tech:android", label: "Android app" }
    IOS@{ icon: "tech:apple", label: "iOS app" }
    WEBC@{ icon: "sd:browser", label: "Web" }
  end
  subgraph L2["Layer 2 · Edge"]
    direction LR
    CDN@{ icon: "sd:cdn", label: "CDN<br/>vector tiles, traffic overlay" }
    API@{ icon: "sd:api", label: "API gateway<br/>directions, probes, tiles" }
  end
  subgraph L3["Layer 3 · Map data (slow loop)"]
    direction LR
    MAPDB@{ icon: "sd:database", label: "Map data<br/>versioned road graph" }
    TB["Tile builder<br/>dirty tiles, per version"]:::service
    TS@{ icon: "sd:object-storage", label: "Tile store<br/>immutable, by version" }
  end
  subgraph L4["Layer 4 · Traffic (fast loop)"]
    direction LR
    KP@{ icon: "tech:kafka", label: "Kafka · probes<br/>by region" }
    MM@{ icon: "tech:flink", label: "Flink · map matching<br/>and segment speeds" }
    SPD@{ icon: "tech:redis", label: "Redis · live speeds<br/>per segment" }
    HIST@{ icon: "sd:database", label: "Historical profiles<br/>per segment, per 15 min" }
  end
  subgraph L5["Layer 5 · Routing"]
    direction LR
    CUST["Customizer<br/>speeds to overlay costs"]:::core
    ROUTE["Routing service<br/>one region per server"]:::hot
    ETA@{ icon: "sd:ml", label: "ETA service<br/>time-dependent + model" }
  end
  AND ==> API
  IOS ==> API
  WEBC ==> API
  AND ==>|"tiles"| CDN
  CDN --> TS
  MAPDB -.->|"new version"| TB
  TB --> TS
  MAPDB -.->|"graph + partition"| ROUTE
  API ==>|"probe batches"| KP
  KP ==> MM
  MM ==> SPD
  HIST -.-> ETA
  SPD --> CUST
  CUST -->|"costs every few s"| ROUTE
  API ==>|"directions"| ROUTE
  ROUTE --> ETA
  SPD -.->|"overlay tiles"| CDN
  class AND,IOS,WEBC client
  class CDN,API edge
  class MAPDB,TS,SPD,HIST store
  class KP queue
  class MM,ETA service

KEY INSIGHTS:

• Split preprocessing by what it depends on. The partition and overlay shape depend only on the map, so they change rarely; the overlay's costs depend on traffic, so they change every few seconds and must be cheap to recompute
• Probes are a stream, speeds are a table. 600,000 points a second come in; a few gigabytes of segment speeds come out, and that table is all routing reads
• Tiles are immutable by version; the live part of the map (traffic colours) is a separate overlay with a short expiry, so the base map can be cached for days

Data Flow: Ananya's Request, Then Her Drive#

%% title: Directions for Ananya, then probes from her drive
sequenceDiagram
  autonumber
  participant A as Ananya's app
  participant G as API gateway
  participant R as Routing, Bengaluru region
  participant E as ETA service
  participant K as Probe stream
  participant M as Map matching
  participant S as Live speeds
  A->>G: Koramangala to the airport, now
  G->>R: Route query with current overlay costs
  R->>R: Search source cell, overlay, target cell
  R->>E: Three alternatives, 38 to 44 km
  E->>E: Speeds expected when she reaches each road
  E-->>A: Hebbal 1 hr 12 min, ORR 1 hr 15, toll road 1 hr 19
  Note over A: she drives, a fix every 5 s
  A-)G: Batch of 6 fixes every 30 s
  G-)K: Append to the region's partition
  K-)M: Fixes to road segments
  M-)S: Segment speeds, each minute

MEANWHILE, IN PARALLEL:

• The customizer recomputes the Bengaluru overlay's costs from live speeds every few seconds, so the next query, Ananya's minute-by-minute route check included, sees the slowdown
• Her phone draws the map from cached vector tiles and refreshes only the small traffic overlay for the tiles on screen

Deep Dive 1: Routing at Continental Scale (Week 1 Concepts: Partitioning; Week 4: Precomputation and Caching)#

This builds on Week 1, Day 1 · Partitioning Deep-Dive.

What is published: the 2015 survey "Route Planning in Transportation Networks" (Bast, Delling, Goldberg, Müller-Hannemann, Pajor, Sanders, Wagner, Werneck) compares these techniques on the same 18-million-junction Western Europe graph and concludes that "one can compute driving directions in milliseconds or less even at continental scale". It reports that Bing Maps uses CRP and that OSRM, the open-source engine for OpenStreetMap, uses CH. Google hasn't published its own algorithm. CRP was designed for what production needs: turn costs and restrictions, several cost functions (fastest, shortest, avoid tolls), queries whose speed doesn't depend on the cost function, and costs that change with traffic.

%% title: Customizable route planning, in three layers
flowchart TD
  MAP@{ icon: "sd:database", label: "Road graph<br/>junctions, segments, turns" }
  PART["Partition, metric-independent<br/>cells with few boundary roads"]:::service
  TOPO["Overlay shape<br/>boundary-to-boundary shortcuts"]:::service
  SPD@{ icon: "tech:redis", label: "Live speeds<br/>per segment" }
  CUST["Customize, every few seconds<br/>shortcut costs, bottom up, in parallel"]:::core
  Q["Query<br/>real roads in the two end cells,<br/>shortcuts everywhere between"]:::hot
  OUT(["Route in ~2 ms<br/>a few thousand junctions scanned"]):::ok
  MAP -.->|"when the map changes"| PART --> TOPO
  TOPO --> CUST
  SPD ==> CUST
  CUST ==> Q --> OUT
  class MAP,SPD store

• Cells at several levels: e.g. neighbourhood-sized cells inside city-sized cells inside state-sized cells. A query uses the finest level only near its two ends and the coarsest in the middle, so a 1,400 km route crosses India mostly on a few hundred shortcuts.
• Good cells have few boundary roads. Rivers, hills and railways do that naturally; the partitioner (PUNCH, in the CRP papers) finds cuts that cross as few roads as possible, which keeps the overlay small.
• A closure is a cost, not a topology change. Setting a segment's cost to infinity and re-customizing its cell takes milliseconds; editing the graph waits for the slow loop.
• Each cost function is just another set of shortcut costs, 0.07 GiB per function on the Western Europe graph, so "avoid tolls" doesn't need a second routing system.

# routing/crp_customize.py

"""
CRP customization for one cell (illustrative). The cell's boundary junctions and
its internal roads never change between map versions; only the costs do. For each
boundary junction, a Dijkstra restricted to the cell gives the cost of the
shortcut to every other boundary junction. Cells are independent, so they run in
parallel; higher levels reuse the shortcut costs of the level below.
"""

import heapq
import math

CLOSED = math.inf


def segment_cost(seg_id: int, length_m: float, speeds: dict, closures: set, default_kmh: float) -> float:
    if seg_id in closures:
        return CLOSED
    kmh = speeds.get(seg_id, default_kmh)
    return length_m / (kmh / 3.6)                     # seconds


def customize_cell(cell, speeds: dict, closures: set) -> dict:
    """Returns {(from_boundary, to_boundary): seconds} for one cell."""
    costs = {}
    for src in cell.boundary:
        dist = {src: 0.0}
        heap = [(0.0, src)]
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist.get(u, math.inf):
                continue
            for seg in cell.out_segments(u):          # only roads inside this cell
                c = segment_cost(seg.id, seg.length_m, speeds, closures, seg.default_kmh)
                nd = d + c + cell.turn_cost(u, seg)
                if nd < dist.get(seg.to, math.inf):
                    dist[seg.to] = nd
                    heapq.heappush(heap, (nd, seg.to))
        for dst in cell.boundary:
            if dst != src:
                costs[(src, dst)] = dist.get(dst, CLOSED)
    return costs

Where the graph lives#

# routing/regions.py

"""
Routing by region (illustrative). Each pool holds one region's whole graph and
overlay in memory; a query never crosses the network inside its search. Cross-
region trips go to the global tier, which keeps only the top overlay level.
"""

from dataclasses import dataclass


@dataclass
class Region:
    name: str
    bbox: tuple            # (min_lat, min_lng, max_lat, max_lng), overlapping neighbours
    pool: str              # e.g. "route-south-asia"


def pick_pool(origin: tuple, dest: tuple, regions: list) -> str:
    def inside(p, r):
        return r.bbox[0] <= p[0] <= r.bbox[2] and r.bbox[1] <= p[1] <= r.bbox[3]
    for r in regions:
        if inside(origin, r) and inside(dest, r):
            return r.pool                       # the common case: both ends in one region
    return "route-global"                       # top-level overlay plus the two end cells

Deep Dive 2: Live Traffic From Phone Probes (Week 8 Concepts: Event Ingestion, Late Data; Week 9: Privacy)#

This builds on Week 8, Day 1 · Event Ingestion and Week 8, Day 4 · Late Data.

%% title: From phone fixes to segment speeds
flowchart TD
  PH@{ icon: "sd:phone", label: "Phones navigating<br/>a fix every 5 s, sent every 30 s" }
  GW@{ icon: "sd:api", label: "Probe endpoint<br/>anonymous session id" }
  KP@{ icon: "tech:kafka", label: "Kafka · probes<br/>partitioned by region" }
  MM["Map matching<br/>HMM, Viterbi over segments"]:::core
  TRIM["Privacy trim<br/>drop trip start and end"]:::bad
  AGG["Segment speeds<br/>1-min windows, median, min devices"]:::hot
  SPD@{ icon: "tech:redis", label: "Redis · live speeds<br/>speed, devices, age" }
  HIST@{ icon: "sd:database", label: "Historical profiles<br/>rebuilt nightly" }
  CUST["Customizer<br/>and traffic overlay"]:::service
  PH ==> GW ==> KP ==> MM --> TRIM --> AGG ==> SPD --> CUST
  KP -.->|"nightly batch"| HIST
  HIST -.->|"where live is thin"| CUST
  class KP queue
  class SPD,HIST store

• Partition the stream by region, so map matching for Bengaluru runs on workers that hold Bengaluru's road graph in memory. A phone's batches carry a short-lived session id, so its fixes land on one worker and can be matched as a sequence.
• Late batches are normal: a phone in an underpass sends a minute of fixes at once. Matching uses event time; the 1-minute window waits a few seconds for stragglers and then closes. A traversal that arrives after its window updates the next one rather than being dropped.
• Privacy is built into the pipeline, following what Google described in 2009: anonymous ids that rotate, reports combined across devices in busy areas, and the start and end of every trip deleted before anything is stored.
• The freshness budget: up to 30 s in the phone's batch + ~10 s to match + a 60 s window + one customization round of under a second ≈ under 2 minutes from cars slowing to routes avoiding them.

# traffic/map_match.py

"""
HMM map matching in the style of Newson and Krumm (2009), much simplified and
illustrative. Candidates are segments near each fix; emission favours segments
close to the fix; transition favours paths whose driving distance matches the
straight-line distance between fixes. Viterbi keeps the best path so far.
"""

import math

SIGMA_M = 15.0        # GPS noise
BETA_M = 50.0         # tolerance for route-vs-straight-line mismatch


def emission(dist_to_segment_m: float) -> float:
    return -0.5 * (dist_to_segment_m / SIGMA_M) ** 2              # log-probability


def transition(route_m: float, straight_m: float) -> float:
    return -abs(route_m - straight_m) / BETA_M


def match(fixes: list, graph) -> list:
    """fixes: [(lat, lng, t)]. Returns the most likely segment for each fix."""
    layers = [graph.candidates(f, radius_m=50) for f in fixes]    # [(seg, dist_m)]
    score = {seg: emission(d) for seg, d in layers[0]}
    back = [{}]
    for i in range(1, len(fixes)):
        straight = graph.haversine_m(fixes[i - 1], fixes[i])
        new, ptr = {}, {}
        for seg, d in layers[i]:
            best, arg = -math.inf, None
            for prev, s in score.items():
                route = graph.driving_distance_m(prev, seg, limit_m=straight * 3)
                if route is None:
                    continue                                      # impossible move
                v = s + transition(route, straight)
                if v > best:
                    best, arg = v, prev
            if arg is not None:
                new[seg], ptr[seg] = best + emission(d), arg
        score, back = new, back + [ptr]
    seg = max(score, key=score.get)
    path = [seg]
    for ptr in reversed(back[1:]):
        seg = ptr[seg]
        path.append(seg)
    return list(reversed(path))

# traffic/segment_speed.py

"""
One speed per segment (illustrative). Live traversals in the last few minutes are
trusted only with enough distinct devices; otherwise the historical profile for
this weekday and quarter-hour fills in. Live readings fade toward history as
they age, so a road that empties out doesn't stay red.
"""

import math
from statistics import median

MIN_DEVICES = 3
WINDOW_S = 300
FADE_S = 240


def live_speed(traversals: list, now: float):
    recent = [t for t in traversals if now - t["at"] <= WINDOW_S and 2 <= t["kmh"] <= 160]
    devices = {t["device"] for t in recent}
    if len(devices) < MIN_DEVICES:
        return None, 0, None
    newest = max(t["at"] for t in recent)
    return median(t["kmh"] for t in recent), len(devices), now - newest


def segment_speed(seg_id: int, traversals: list, history, now: float, weekday: int, quarter: int) -> float:
    hist = history.kmh(seg_id, weekday, quarter)
    kmh, n, age = live_speed(traversals, now)
    if kmh is None:
        return hist
    trust = (n / (n + 5)) * math.exp(-age / FADE_S)              # more devices, fresher: more trust
    return trust * kmh + (1 - trust) * hist

Deep Dive 3: Predicting the Arrival Time (Week 8 Concepts: Streaming vs Batch; Week 7: Ranking Models)#

This builds on Week 8, Day 2 · Streaming vs Batch.

What Google and DeepMind have published: Google's 2020 post says Maps analyses "historical traffic patterns for roads over time" and combines them with live traffic conditions, then uses machine learning to forecast. During 2020's lockdowns, with up to a 50% drop in worldwide traffic, it began "automatically prioritizing historical traffic patterns from the last two to four weeks, and deprioritizing patterns from any time before that". DeepMind's post describes Supersegments, "multiple adjacent segments of road that share significant traffic volume", a graph neural network trained on them, and the training difficulty: batches ranged from two-node graphs to graphs of more than 100 nodes, which DeepMind handled with MetaGradients to adapt the learning rate and a combination of several loss functions.

%% title: Timing one route
flowchart TD
  RT(["Route<br/>412 segments, 38 km"]):::client
  WALK["Walk the route in order<br/>clock starts at departure"]:::core
  LIVE@{ icon: "tech:redis", label: "Live speeds<br/>next ~10 minutes" }
  HIST@{ icon: "sd:database", label: "Historical profile<br/>weekday, quarter-hour" }
  TURN["Junction and turn delays<br/>signals, tolls, crossings"]:::service
  GNN@{ icon: "sd:ml", label: "Correction model<br/>per Supersegment" }
  OUT(["ETA 1 hr 12 min<br/>and a likely range"]):::ok
  RT --> WALK
  LIVE -.-> WALK
  HIST -.-> WALK
  TURN -.-> WALK
  WALK --> GNN --> OUT
  class LIVE,HIST store

• Route choice and ETA use the same speeds where they can. The routing query runs on the current customization (live speeds plus history where live is thin); the ETA service then times the two or three alternatives with the time-dependent walk and orders them by ETA. A route that looks fastest now but meets the 6:15 Hebbal jam can drop to second.
• "Leave at 6 pm" is a separate customization built from historical profiles for that weekday and time, refreshed every 15 minutes; the query and the walk are the same.
• A range, not a point: the same model can predict the spread of past trips like this one. Showing "1 hr 10 to 1 hr 20" when the road is unpredictable is more honest than one number.
• When the model is down, the walk alone still gives a sensible ETA. The model corrects; it never replaces the sum.

# eta/predict.py

"""
A time-dependent ETA (illustrative). Each segment's speed is the one expected
when the driver reaches it: live for the near future, history further out, a
blend in between. A learned correction per Supersegment adjusts the sum.
"""

NEAR_S = 600        # trust live speeds for the next 10 minutes
FAR_S = 1800        # trust history from 30 minutes out


def blend(live_kmh, hist_kmh: float, ahead_s: float) -> float:
    if live_kmh is None or ahead_s >= FAR_S:
        return hist_kmh
    if ahead_s <= NEAR_S:
        return live_kmh
    w = (FAR_S - ahead_s) / (FAR_S - NEAR_S)
    return w * live_kmh + (1 - w) * hist_kmh


def eta_seconds(route: list, depart_at: float, live, history, turns, model) -> float:
    t = depart_at
    for prev, seg in zip([None] + route[:-1], route):
        ahead = t - depart_at
        kmh = blend(live.kmh(seg.id), history.kmh_at(seg.id, t), ahead)
        t += seg.length_m / max(kmh, 3.0) * 3.6 + turns.delay_s(prev, seg)
    raw = t - depart_at
    return raw * model.correction(route, depart_at)          # ~1.0; falls back to 1.0 if unavailable

Deep Dive 4: Vector Tiles, Quadkeys and Caching (Week 4 Concepts: Multi-Tier Caching, Cache Invalidation)#

This builds on Week 4, Day 5 · Multi-Tier Caching and Week 4, Day 2 · Cache Invalidation.

%% title: From a map edit to a tile on screen
flowchart TD
  ED(["Map edits<br/>100 million a day, most are places"]):::client
  MAPDB@{ icon: "sd:database", label: "Map data<br/>versioned" }
  DIRTY["Dirty quadkeys<br/>edit tile + 16 ancestors, deduplicated"]:::core
  TB["Tile builder<br/>rebuild dirty tiles only"]:::service
  TS@{ icon: "sd:object-storage", label: "Tile store<br/>v1843/2130231… immutable" }
  EDGE@{ icon: "sd:cdn", label: "CDN edges<br/>95%+ hits" }
  PH@{ icon: "sd:phone", label: "Phone<br/>draws vectors, caches areas" }
  TRF["Traffic overlay<br/>per tile, expires in ~60 s"]:::hot
  ED --> MAPDB --> DIRTY --> TB --> TS --> EDGE --> PH
  TRF -.-> EDGE
  class MAPDB,TS store
  class EDGE edge

• Most of the 100 million daily updates don't touch geometry: opening hours, a new café, a phone number. Those are place data fetched with the place, not baked into tiles. Geometry changes are batched into a new map version every few minutes to hours.
• The phone keeps a version pointer: after an update it asks for the new version's manifest and fetches only tiles whose content changed; the rest are already in its cache under the same content hash.
• Traffic stays out of base tiles: the overlay holds a colour per visible segment for one tile, expires in about a minute, and is tiny. The base tile can be cached for days.
• Popular tiles are tiny in number: a city centre at every zoom is a few thousand tiles. CDN edges keep them hot, and a major event that brings a crowd to one stadium is still one set of tiles.

# tiles/quadkey.py

"""
Tile names in the scheme Microsoft documents for Bing Maps (illustrative Python).
Web Mercator, 256-pixel tiles, one base-4 digit per level: the quadkey of a tile
starts with the quadkey of its parent.
"""

import math

MAX_LAT = 85.05112878


def tile_xy(lat: float, lng: float, level: int) -> tuple:
    lat = max(-MAX_LAT, min(MAX_LAT, lat))
    s = math.sin(math.radians(lat))
    x = (lng + 180) / 360
    y = 0.5 - math.log((1 + s) / (1 - s)) / (4 * math.pi)
    n = 1 << level
    return min(n - 1, int(x * n)), min(n - 1, int(y * n))


def quadkey(tx: int, ty: int, level: int) -> str:
    digits = []
    for i in range(level, 0, -1):
        mask = 1 << (i - 1)
        d = (1 if tx & mask else 0) + (2 if ty & mask else 0)
        digits.append(str(d))
    return "".join(digits)                      # quadkey(3, 5, 3) == "213"


def dirty_tiles(lat: float, lng: float, max_level: int = 16) -> list:
    """An edit at one point dirties its deepest tile and every ancestor."""
    qk = quadkey(*tile_xy(lat, lng, max_level), max_level)
    return [qk[:k] for k in range(1, max_level + 1)]


def tile_url(version: int, qk: str) -> str:
    return f"https://tiles.example.com/v{version}/{qk}.mvt"     # immutable: cache forever

Ananya's Evening#

Edge Cases#

Monitoring Dashboard#

SLOs for the Platform#

The interviewer looks out of the window. "One more."

Summary: Concepts Applied from 10-Week Course#

Why Google Maps Matters#

Self-Assessment Checklist#

After studying this case study, you should be able to:

Routing:

Traffic and ETAs:

Tiles and operations:

Sources#

Google and DeepMind:

• Blog

  Miriam Daniel — Google Maps celebrates 20 years with 20 favorite features (more than 2 billion users a month; 1 trillion km of directions in 2024; 250 million places; 500 million contributors; 100 million updates a day), 6 February 2025: https://blog.google/products-and-platforms/products/maps/20-years-google-maps-20-features/

• Blog

  Johann Lau — Google Maps 101: How AI helps predict traffic and determine routes (1 billion km driven a day, 220+ countries and territories, ETAs accurate for over 97% of trips, aggregate location data, historical patterns, last two to four weeks prioritised, up to 50% drop in traffic, route factors), 3 September 2020: https://blog.google/products/maps/google-maps-101-how-ai-helps-predict-traffic-and-determine-routes/

• Blog

  Oliver Lange, Luis Perez — Traffic prediction with advanced Graph Neural Networks (Supersegments, up to 50% better real-time ETAs, 51% in Taichung, MetaGradients, combined losses), DeepMind, 3 September 2020: https://deepmind.google/blog/traffic-prediction-with-advanced-graph-neural-networks/

• Blog

  Dave Barth — The bright side of sitting in traffic: Crowdsourcing road congestion data (anonymous speed and location, combining reports, deleting trip start and end points), August 2009: https://googleblog.blogspot.com/2009/08/bright-side-of-sitting-in-traffic.html

• Blog

  Michael Siliski — The next generation of mobile maps (vector graphics, 100 times less data across zoom levels, almost 70% less mobile data), 16 December 2010: https://maps.googleblog.com/2010/12/next-generation-of-mobile-maps.html

• Blog

  Andrew Miller — Under the hood of Google Maps 5.0 for Android (more than 360 billion tiles at 20 zoom levels; vector tiles as blueprints; each works across several zoom levels), 17 December 2010: https://maps.googleblog.com/2010/12/under-hood-of-google-maps-50-for.html

Research and documentation:

• Paper

  Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato Werneck — Route Planning in Transportation Networks (Western Europe: 18.0 million junctions, 42.5 million arcs; Dijkstra 2.2 s; CH 0.11 ms; CRP 1.65 ms, customization 0.37 s on 12 cores, 36 ms with GPUs; Bing Maps uses CRP, OSRM uses CH), 2015: https://arxiv.org/abs/1504.05140

• Paper

  Paul Newson, John Krumm — Hidden Markov Map Matching Through Noise and Sparseness, ACM SIGSPATIAL GIS 2009: https://www.microsoft.com/en-us/research/publication/hidden-markov-map-matching-noise-sparseness/

• Blog

  Joe Schwartz — Bing Maps Tile System (Mercator, 256-pixel tiles, levels 1 to 23, latitude clipped at 85.05112878, quadkeys), Microsoft Learn: https://learn.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system

Reporting:

• Blog

  CNN — Artist uses 99 phones to trick Google into traffic jam alert (Simon Weckert, Berlin), February 2020: https://amp.cnn.com/cnn/style/article/artist-google-traffic-jam-alert-trick-scli-intl

Design note: the architecture, code, thresholds, rates, sizes and dashboards here are an illustrative design for the problem, not a description of Google's internal systems beyond what Google and DeepMind have published. Estimates in Phase 2 are labelled as assumptions or estimates.

Further Reading#

Related systems to study:

• Read

  Uber (Bonus Problem 9 in this series): H3 cells, driver location pings and ETAs for matching

• Read

  Swiggy (Bonus Problem 17): rider location ingest and the ETA as a calibrated distribution

• Read

  Blinkit (Bonus Problem 12): store density, road distance and promise times

• Book

  Google Search (Bonus Problem 5): another system that wins by precomputing an index

Papers:

• Read

  Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling — Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (WEA 2008)

• Read

  Daniel Delling, Andrew Goldberg, Thomas Pajor, Renato Werneck — Customizable Route Planning (SEA 2011) and Customizable Route Planning in Road Networks (Transportation Science, 2017)

Foundational concepts (this course):

• Read

  Week 1, Day 1 — Partitioning Deep-Dive

• Read

  Week 4, Day 2 — Cache Invalidation

• Read

  Week 4, Day 5 — Multi-Tier Caching

• Read

  Week 8, Day 1 — Event Ingestion

• Read

  Week 8, Day 2 — Streaming vs Batch

• Read

  Week 8, Day 4 — Late Data

"The map changes a hundred million times a day and the roads change speed every minute; precompute the first, stream the second, and time every road for when you'll reach it."