Rebuilding an entire routing graph because a handful of ways changed is the default behaviour of most pipelines, and for a city extract it is entirely reasonable. Past a certain size it stops being reasonable: a national graph that takes four hours to build cannot be refreshed hourly, and the freshness ceiling is set by the build rather than by the data. This page covers the technique that breaks that coupling — rebuilding only the partitions a change set actually touched — as the final stage of the pipeline described in OSM data freshness and incremental updates, and it depends on the partitioned architecture introduced in OSM Graph Architecture & Network Modeling.

The idea is straightforward and the details are where it goes wrong. Changed objects map to partitions; partitions whose input is unchanged reuse their previous artefact; everything else rebuilds. The two failure modes are a dirty-set that is too small — producing a graph with stale regions — and a cache key that is too loose, producing hits that should have been misses.

When to use this approach

Incremental rebuilds earn their complexity when:

  • The full build exceeds the desired refresh interval. This is the defining condition. If a full rebuild takes twenty minutes and you refresh daily, none of this is worth writing.
  • The graph is already partitioned. Multi-level Dijkstra deployments have partitions for their own reasons, and reusing them for rebuild scoping is nearly free. Building a partitioning scheme purely to enable incremental rebuilds is a much larger commitment.
  • Change sets are spatially concentrated. Most OSM intervals are: edits cluster around active mappers and recent imports. When a change set is genuinely uniform across the extract — as after a national retagging — the dirty set is everything and the technique degenerates to a full rebuild, which is the correct outcome rather than a failure.
  • Artefact storage is cheap relative to compute. Reuse requires keeping the previous artefacts, so the trade is disk for CPU.

Skip it when the engine precomputes a global hierarchy. Contraction hierarchies produce shortcuts that can connect distant parts of the graph, so a local change has non-local consequences and there is no sound way to rebuild a subset.

From changed objects to a dirty partition set A grid of twelve partitions holds changed objects in three of them. Buffering the partition boundaries marks two additional neighbouring partitions dirty because changes fall within one edge length of the shared boundary, leaving seven partitions clean and reusable. Twelve partitions, 1 840 changed objects, five partitions to rebuild contains changed objects — rebuild within the boundary buffer — rebuild clean — reuse the cached artefact 5 of 12 rebuilt, so the run costs roughly 42 % of a full build — less again once run in parallel The two gold partitions hold no changes at all. They rebuild because a change on the far side of their shared boundary alters routes that cross it.

Implementation

The dirty set is a spatial join, and the only subtlety is the buffer.

# requires: geopandas, shapely (pip install geopandas shapely)
import geopandas as gpd
from shapely.geometry import Point


def dirty_partitions(
    changed: list[tuple[float, float]],
    partitions: gpd.GeoDataFrame,
    *,
    buffer_m: float = 400.0,
) -> set[str]:
    """Partitions containing a change, or within buffer_m of one."""
    if not changed:
        return set()

    metric = partitions.estimate_utm_crs()
    parts = partitions.to_crs(metric).copy()
    # Grow each partition so a change just outside its boundary still marks it
    parts["geometry"] = parts.geometry.buffer(buffer_m)

    pts = gpd.GeoDataFrame(
        geometry=[Point(lon, lat) for lon, lat in changed],
        crs="EPSG:4326",
    ).to_crs(metric)

    hit = gpd.sjoin(pts, parts, predicate="within", how="inner")
    return set(hit["partition_id"].unique())

Buffering in a projected CRS is not optional — a buffer expressed in degrees is a different distance at every latitude, and the whole point of the buffer is that it corresponds to a real length on the ground.

The cache key is the second half. Hashing the partition’s input alone is the mistake that produces stale artefacts, because the output also depends on every parameter the builder consulted.

# requires: none beyond the standard library
import hashlib
import json
from pathlib import Path


def artefact_key(
    partition_input: Path,
    cost_config: dict,
    builder_version: str,
) -> str:
    """Content hash covering the input and everything that transforms it."""
    digest = hashlib.sha256()

    with partition_input.open("rb") as fh:
        for block in iter(lambda: fh.read(1 << 20), b""):
            digest.update(block)

    # Sorted keys so an equivalent config always hashes identically
    digest.update(json.dumps(cost_config, sort_keys=True).encode())
    digest.update(builder_version.encode())
    return digest.hexdigest()

Including the builder version is what makes a code change invalidate the cache. Without it, a fix to the tag-mapping logic silently fails to reach any partition whose input did not also change — which is the majority of them, and is exactly the situation in which someone concludes the fix “did not work”.

With both pieces in place, the rebuild loop reduces to a filter and a parallel map:

# requires: concurrent.futures (stdlib)
from concurrent.futures import ProcessPoolExecutor

def rebuild_incremental(all_partitions, dirty, cache, build_fn, *, workers=4):
    """Rebuild dirty partitions in parallel, reuse cached artefacts otherwise."""
    todo, reused = [], []
    for part in all_partitions:
        key = artefact_key(part.input_path, part.cost_config, part.builder_version)
        if part.id not in dirty and key in cache:
            reused.append(cache[key])
        else:
            todo.append((part, key))

    with ProcessPoolExecutor(max_workers=workers) as pool:
        built = list(pool.map(build_fn, [p for p, _ in todo]))

    for (_, key), artefact in zip(todo, built):
        cache[key] = artefact
    return reused + built

Note that a partition is rebuilt if it is dirty or if its key misses. The two conditions catch different things — the dirty set catches data changes, the key catches configuration and code changes — and relying on either alone leaves a gap.

What has to go into the cache key The cache key hashes the partition input, the cost configuration and the builder version. Omitting the config produces stale hits after a coefficient change; omitting the builder version produces stale hits after a code fix, which is why a fix can appear not to work. Three inputs, one key — omit any and the cache lies partition input bytes cost config, sorted builder version sha256 → key omit the input — every partition looks clean forever omit the config — a retuned coefficient never reaches the graph omit the builder version — a bug fix appears not to work all three present — a hit genuinely means nothing changed The third omission is the cruel one: the fix is correct, the tests pass on a fresh build, and production keeps serving the old behaviour. A partition rebuilds when it is dirty OR when its key misses — the two conditions catch different classes of change.

Key parameters and tuning

Parameter Recommended value Notes
buffer_m ≈ longest edge in the graph Too small leaves stale boundary routes; too large marks everything dirty
Partition count 40–200 for a national extract Fewer means coarse rebuild scoping; more means boundary-node overhead dominates
Cache key inputs data + config + builder version Omitting any one produces stale hits that are extremely hard to diagnose
Parallel workers physical cores − 1 Each partition build is memory-hungry; oversubscribing swaps rather than speeds up
Retained artefact versions 2–3 per partition Enough to roll back one bad build without unbounded storage growth
Full-rebuild fallback dirty set above 70 % Past that point, coordination overhead exceeds the saving
Boundary revalidation every run Cheap, and the only check that catches a bad stitch

Integration points

Consuming the change classification. The changed-coordinate list comes from the classification stage described in OSM data freshness and incremental updates. Feeding it the full changed-object set rather than the routing-relevant subset makes the dirty set larger than it needs to be without making it safer, since irrelevant changes by definition do not alter the built artefact.

Respecting the tag-change gate. A significant tag-distribution shift, as detected in detecting breaking tag changes between PBF snapshots, usually means the cost configuration needs revisiting. When that happens the config hash changes and every partition misses, which is the correct behaviour: a changed cost surface is a full rebuild by definition.

Feeding the connectivity audit. The stitched result must clear the same strongly connected component check as a full build, described in graph fragmentation prevention in OSM data. A bad stitch shows up there as a sudden crop of small components along partition boundaries, which is a distinctive enough signature to diagnose from the audit output alone.

Where an incremental rebuild stops paying Total build time is plotted against the proportion of partitions in the dirty set. The incremental path is far cheaper at low dirty shares, converges with the full rebuild near seventy percent, and exceeds it beyond that because of coordination and stitching overhead. Total build time against dirty-partition share 0 % 50 % 100 % 4 h 0 full rebuild — constant incremental 70 % — fall back to a full rebuild Above the crossover, coordination and stitching overhead exceeds the work saved — so the fallback is a performance decision, not just a simplicity one. Most intervals sit far to the left; the fallback exists for import days and mass retagging, which is exactly when you want the simplest possible path.

Validation checklist

  • The stitched graph matches a full rebuild. Periodically build both from the same extract and compare edge sets. They must be identical; any divergence is a bug in the dirty set or the stitch, and it will grow.
  • Boundary components are unchanged. Count strongly connected components before and after. New small components clustered along partition boundaries mean boundary nodes were not restitched correctly.
  • A config change invalidates every partition. Change one cost coefficient and confirm the cache misses everywhere. If it does not, the key is hashing the wrong things.
  • The dirty set is a superset of the changed set. Every partition containing a changed object must appear, plus its buffered neighbours. Assert this directly rather than trusting the join.
  • The fallback fires. Feed a synthetic change set touching most partitions and confirm the pipeline takes the full-rebuild path rather than grinding through a near-total incremental run.