Edge Geospatial IoT Gateway Processing

Contraction hierarchies in a 256 MB footprint

Plain Dijkstra over a regional road network on a gateway takes seconds, which is fine for a route computed once and useless for one recomputed at every junction. Contraction hierarchies make the same query take milliseconds by preprocessing the graph into a structure that lets a search skip almost all of it — at the cost of a preprocessing step and extra edges. This guide fits that structure into a 256 MB node, inside fallback routing and offline navigation and the Core Edge GIS Fundamentals envelope.

What contraction buys, and what it costs

The preprocessing assigns every node a rank and then removes nodes one at a time in rank order. When a node is removed, any shortest path that went through it is preserved by adding a shortcut edge between its neighbours, carrying the combined weight. After every node has been contracted, the graph contains the original edges plus a set of shortcuts.

A query then runs two searches — forward from the origin, backward from the destination — and each one is only ever allowed to move to a higher-ranked node. That restriction is what makes it fast: instead of expanding outward across the whole region, both searches climb quickly into the sparse upper levels of the hierarchy and meet there.

The costs are two. Preprocessing takes minutes to hours depending on graph size, which means it happens at build time, not on the device. And the shortcuts inflate the edge count — typically by 30–60% for a road network — which is the number that decides whether the result fits in the memory budget.

A bidirectional upward search against a plain Dijkstra expansion Two searches over the same origin and destination. Plain Dijkstra expands a broad circular frontier from the origin that grows until it reaches the destination, settling tens of thousands of nodes. The contraction hierarchy search runs two narrow searches, one forward from the origin and one backward from the destination, each moving only to higher-ranked nodes, so both climb into a sparse upper level and meet there after settling a few hundred nodes. Same route, two search shapes Dijkstra — 34 000 nodes settled, 2.9 s rank 0–2rank 3–5rank 6–8rank 9+ meet CH — 340 nodes settled, 6 ms
The rank ordering is the entire mechanism: both searches are forbidden from going downhill, so neither can expand across the region.

The memory budget

Fitting the structure is arithmetic. For a regional network of 1.2 million nodes and 2.6 million edges:

Component Layout Bytes
Node ranks uint32 per node 4.8 MB
Edge heads uint32 per edge 10.4 MB
Edge weights uint32 per edge, decimetres 10.4 MB
Shortcut middles uint32 per shortcut, for unpacking 4.2 MB
CSR offsets uint32 per node + 1 4.8 MB
Original edges + shortcuts ×1.45 inflation applied above —
Total memory-mapped, read-only 34.6 MB

That fits comfortably, and it fits because every array is a flat, fixed-width, memory-mappable buffer with no per-node objects — the same discipline as the packed R-tree. The same graph as an adjacency-list object graph in Python would be well over a gigabyte, which is the reason this structure is built at provisioning and shipped as a file rather than constructed on the device.

The query 

# ch_query.py — bidirectional upward search over a memory-mapped CH graph.
# All arrays are numpy-free flat buffers via mmap; nothing per-node is allocated.
# One instance per query is cheap: the visited maps are dicts sized by the
# search, which settles hundreds of nodes rather than tens of thousands.
import heapq
import struct


class CHGraph:
    """Read-only, memory-mapped. Arrays are uint32 little-endian:
    offsets[n+1], heads[m], weights[m], ranks[n], middles[m]."""

    __slots__ = ("offsets", "heads", "weights", "ranks", "middles", "n")

    def __init__(self, mm, n: int, m: int):
        u32 = struct.Struct("<I")
        base = 0
        self.offsets = memoryview(mm)[base:base + 4 * (n + 1)].cast("I")
        base += 4 * (n + 1)
        self.heads = memoryview(mm)[base:base + 4 * m].cast("I")
        base += 4 * m
        self.weights = memoryview(mm)[base:base + 4 * m].cast("I")
        base += 4 * m
        self.ranks = memoryview(mm)[base:base + 4 * n].cast("I")
        base += 4 * n
        self.middles = memoryview(mm)[base:base + 4 * m].cast("I")
        self.n = n

    def _search(self, source: int, upward: bool):
        """One direction of the bidirectional search. Yields settled distances.
        Only edges to higher-ranked nodes are followed, which is what bounds
        the frontier to a few hundred nodes on a regional graph."""
        dist = {source: 0}
        queue = [(0, source)]
        settled = {}
        while queue:
            d, u = heapq.heappop(queue)
            if u in settled:
                continue
            settled[u] = d
            ru = self.ranks[u]
            for e in range(self.offsets[u], self.offsets[u + 1]):
                v = self.heads[e]
                if self.ranks[v] <= ru:
                    continue                       # never go downhill
                nd = d + self.weights[e]
                if nd < dist.get(v, 1 << 31):
                    dist[v] = nd
                    heapq.heappush(queue, (nd, v))
        return settled

    def shortest_distance(self, source: int, target: int):
        """Meeting-node search. Returns (distance, meeting_node) or None."""
        fwd = self._search(source, upward=True)
        bwd = self._search(target, upward=True)     # the reversed graph is symmetric here
        best, meet = None, None
        for node, d in fwd.items():
            b = bwd.get(node)
            if b is None:
                continue
            total = d + b
            if best is None or total < best:
                best, meet = total, node
        return None if best is None else (best, meet)

The two searches are independent, which matters on a constrained device for a reason unrelated to speed: each one can be run, its result kept, and the other run afterwards, so peak memory is one frontier rather than two. On a device where the routing engine shares memory with the rest of the pipeline, that halves the transient cost of a query.

Preprocessing inflation against query cost for four contraction orders Four node-ordering heuristics compared on the same regional graph. No contraction leaves 2.6 million edges and settles 34 000 nodes per query. A simple degree-based order gives 3.1 million edges and 2 100 nodes settled. An edge-difference order gives 3.4 million edges and 620 settled. Edge difference combined with a contracted-neighbours term gives 3.8 million edges — a 45 percent inflation — and 340 settled, which is the configuration the memory table above assumes. More shortcuts, smaller searches — the trade is memory for latency edges after contractionnodes settled per query no contractiondegree orderedge differenceedge diff + neighbours 2.6 M3.1 M3.4 M3.8 M · +45% 34 0002 100620340 The ordering heuristic is a build-time choice; the device only ever sees its output.
Past the third row the returns diminish sharply while the memory keeps growing, which is where a constrained device should stop.

Constraint validation

Constraint Expected impact Mitigation
RAM An object graph would exceed the budget by an order of magnitude Flat uint32 arrays, memory-mapped; the kernel pages what the search touches
Build time Contraction takes minutes to hours Done at provisioning on a build host; the device receives a file
Query latency A route recomputed per junction must be fast Bidirectional upward search settles hundreds of nodes, not tens of thousands
Flash The structure is 30–60% larger than the raw graph Budgeted explicitly; the inflation is the price of the latency
Power A long search keeps the SoC awake 6 ms per query is negligible even on a duty-cycled node

Gotchas and edge cases

  • Turn restrictions are not free. A plain CH over a node-based graph cannot express “no left turn here”. Encoding restrictions requires either an edge-expanded graph — which multiplies the node count by the average degree — or a post-search repair pass. Decide which before building, because the graph layout differs.
  • The path is not the edges you searched. Shortcuts have to be unpacked recursively into their original edges to produce a drivable route. The middles array is what makes that possible, and forgetting it produces a correct distance with an undrivable geometry.
  • Dynamic weights break the hierarchy. A CH is built for one weight function. Changing edge weights — for a road closure, or for live traffic — invalidates the shortcuts. The workable pattern on a gateway is a static CH plus a small overlay of closures handled by a repair pass, exactly as the fallback routing guide describes for closed segments.
  • Memory-mapped does not mean free. A query touches a few hundred nodes but faults in whole 4 KB pages, so the resident set after a query is larger than the data used. On a device that queries rarely, the kernel reclaims it; on one that queries constantly, budget for a resident working set of a few megabytes.
  • The rank array must match the edge arrays. A graph file built from one node ordering and ranks from another produces a search that terminates and returns wrong answers. Bind them with a build id in the file header and check it at load.

Verifying a build

Validate three properties on the build host, before the file ships. Distance agreement: for a few thousand random origin-destination pairs, compare the CH result against a plain Dijkstra over the original graph. They must match exactly — CH is not an approximation, and any difference is a bug in the contraction. Unpacking correctness: for a sample of routes, unpack the shortcuts and confirm the resulting edge sequence is connected and its weights sum to the reported distance. Rank monotonicity: assert every shortcut connects two nodes both ranked above the node it replaced.

Those three checks take a few minutes and they are the only thing standing between a subtly broken preprocessing run and a fleet routing confidently along paths that do not exist.

Handling closures without rebuilding

A road closure invalidates any shortcut whose underlying path crosses it, and rebuilding the hierarchy on the device is not an option. Three practical approaches exist and they suit different closure frequencies.

Search-time filtering keeps a small set of closed edge ids and skips any shortcut whose unpacked path touches one. Correct, and expensive: it requires unpacking during the search rather than after it, which costs most of the CH advantage on a route near a closure.

Penalty overlay leaves the hierarchy intact and applies a large additive penalty to affected shortcuts rather than removing them. The route avoids the closure unless there is no alternative, which is usually the desired behaviour anyway, and the search stays fast. The cost is that the penalty is approximate — a shortcut penalised for containing a closed edge might have had an unaffected alternative path.

Local repair runs the CH query normally, checks the unpacked route against the closure set, and if it is affected, re-runs a plain bidirectional Dijkstra restricted to a corridor around the original route. Exact, and bounded, because the corridor is small.

The third is what most field deployments end up with, because closures are rare enough that paying for a repair on the affected minority of queries is cheaper than slowing all of them down.

Three closure strategies against query cost and exactness Search-time filtering costs 41 milliseconds per query because it unpacks shortcuts during the search, and is exact. Penalty overlay costs 7 milliseconds, the same as an unaffected query, and is approximate because a penalised shortcut may have had a clear alternative. Local repair costs 6 milliseconds for the 96 percent of queries unaffected by a closure and 34 for the affected minority, and is exact. The weighted average for local repair is 7.1 milliseconds. Closures are rare — pay for them only on the queries they touch search-time filtering 41 ms every query exact — but pays on all queries penalty overlay 7 ms every query approximate — may avoid a clear road local repair 6 ms for 96%, 34 ms for the rest exact · 7.1 ms weighted average corridor-restricted Dijkstra only where the route is affected
The bottom row is exact and costs almost exactly what the approximate option costs, because the expensive path is taken so rarely.

Related in Fallback Routing & Offline Navigation