Recently, within our particular application of Foundry, we’ve had interest in supporting this type of abstract query in real-time:
“Find objects that fall within a specified driving time of one fixed set of points, but not within that driving time of another fixed set of points.”
A radius may not sufficiently represent this area. Road networks, natural barriers, topology, and access constraints can all make the actual reachable region significantly different from a circle (an easy example here is the existence of highways, the actual shape of what can be reached tends to look more like a starfish than a circle). We therefore want a low-overhead but still shape-accurate way to define catchment areas around a fixed set of points.
One could imagine that this query capability could be useful in various contexts (EMS dispatch, utility planning, retail site planning to name a few). Resolving this query requires us to know not only the driving time from arbitrary point A → point B, but the entire region reachable within x minutes of point A: an isochrone. We then can leverage the Ontology to apply set operations over this isochrone arbitrarily, which also proved to be an interesting exercise in Ontology design.
Example of an isochrone. SOURCE: https://valhalla.github.io/valhalla/api/isochrone/
For our specific use case, we do not mind some graininess within our isochrones because the result is ultimately used to determine whether objects fall inside or outside an already approximate catchment area. This loosening of the requirements gives us room to bucket aggressively, which can then be persisted as Objects in the Ontology with very little overhead at massive scale.
Options for Isochrone and Drive-Time Estimation
We need a method of defining the region reachable within a driving time of x minutes from an arbitrary point A.
Commercial mapping APIs
Commercial mapping APIs are often the first reaction and may provide both point-to-point estimation and isochrone generation.
However:
- They may not be scalable when a single query needs to evaluate a large fixed set of points.
- They can become expensive without caching results.
- Caching introduces additional technical complexity:
-
- Cache eviction (?)
- Cold cache slots
- Refresh rates
- Invalidation
- Version consistency
- Coordinates or other location information may need to leave Foundry.
- Isochrone support may be newer or less mature than point-to-point routing.
Open-source, self-hosted alternatives
Open-source alternatives that we considered include:
- Valhalla
- pgRouting, particularly for systems already using PostGIS
- OSRM, particularly for point-to-point routing
Valhalla specifically:
- Has a well-maintained Python library.
- Performs well for flexible isochrones.
- Supports dynamic and easily modifiable costing models.
- Has a tiling system, which becomes important for memory considerations when running across large geographic regions.
- Is self-hosted, so compute and storage are the primary costs.
- Scales well for the data volumes involved.
- Allows coordinates and road-network data to remain within Foundry.
Valhalla struggles with:
- Live traffic. It has capabilities to adjust for traffic, but requires a stream of traffic data to do so.
-
- Live traffic may not be necessary for this class of query.
- A stable measure of distance and time may be preferable to one that changes hour to hour, especially when supporting precomputed catchment areas.
- Point-to-point speed. OSRM’s contraction hierarchies are less flexible but very fast for direct routing.
-
- This is not a primary requirement for this feature; we need isochrones and their contours rather than high-volume point-to-point routes.
For our needs, Valhalla proved to be good enough.
Bucketing with H3 Geospatial Indexing
The H3 geospatial index is a method of hierarchically tiling the world into hexagonal grids of varying resolution.
For our purposes, the index exists as the link between objects associated with a tile and the estimated driving time from that tile to a fixed reference point. An H3 index therefore serves as the bridge between:
- A driving-time catchment around a reference point
- A map tile
- Any objects associated with that tile
This avoids repeatedly calculating routing distance from every object to every reference point.
Nearest-point optimization
Each H3 tile only needs to store one driving time for each logical collection of reference points: the time to the nearest point in that collection.
This prevents an n × m explosion between a large fixed set of reference points and a much larger set of objects, which would be both infeasible and wasteful.
Only storing the nearest point comes with a tradeoff. If a query selects an arbitrary subset of points from a collection, some tiles may be omitted because they were assigned to another, closer point in the same collection.
This can be an acceptable tradeoff where:
- Proximity to the nearest point is the dominant behavior.
- Queries usually operate over the entire point collection.
- A subset requiring independent treatment can be split into its own collection.
Tie-breaking
If driving times are bucketed, for example, into intervals of two minutes, there will be cases where a tile has an equal drive-time band to two reference points and must be tie-broken.
In this case, we choose the point with the minimum haversine distance between the H3 centroid and the point’s coordinates.
An arbitrary tie-breaker creates checkerboarding in disputed regions, which may not be desirable.
H3 resolution
We settled on H3 resolution 8, approximately 0.7 km², to balance:
- Space efficiency
- Boundary sharpness
- Query performance
- Acceptable spatial error
In implementation and precomputation, H3 also proves useful as a partition key. Its hierarchical structure helps bound Spark executor memory, as geographically concentrated sets tend to share many tiles.
Precomputation and Ontology Structure
Only tiles within a configured maximum driving time of a reference point are precomputed. This serves to upper-bound the total tile count.
The maximum can be expanded if necessary, but doing so increases space usage and compute costs approximately in proportion to the resulting catchment area.
Within that maximum, catchments are precomputed at fixed bands. For example:
2, 4, 6, 8, ..., 60 minutes
A query can then request any supported range by filtering on drive_time_min. Additional precision can be obtained by using narrower bands, with a corresponding increase in storage and computation.
The Ontology is designed to preserve fast query times:
REFERENCE POINT ← has-a → CATCHMENT CELL ← is-a → H3 TILE ← contains → OBJECT
This double-link structure separates:
- The fixed reference point
- The precomputed drive-time relationship
- The reusable spatial tile
- Objects associated with that tile
The catchment cell is the bridge between reference points and H3 tiles. Objects do not need a direct relationship to every reference point; they only need to be associated with their spatial tile. This allows for append operations without incurring a reindex.
Implementation Specifics
Before precomputation begins, it is necessary to ingest road-level data (ie: .osm.pbf files) and compile it into a Valhalla-compatible .tar file.
This converts raw road-network data received from OpenStreetMap into partitionable tiles that can be distributed to executors in a Spark job.
Our goal is to create a Spark job that produces an Object called [COLLECTION] Catchment Cell with the following schema:
| Column | Value |
|---|---|
| catchment_cell_key | String primary key: {point_key};{h3_index} |
| h3_index | String, H3 resolution 8 |
| point_key | String identifying the fixed reference point |
| point_collection | String identifying the logical collection of points |
| drive_time_min | Integer drive-time band, such as 2, 4, 6, …, 30 |
The key optimization is to leverage the hierarchical nature of H3 indexes to roll up resolutions and localize the Valhalla tiles an executor needs to pull.
We partition each reference point into its broader neighborhood. For example, an H3 index at resolution 5. This allows us to reuse many Valhalla tiles that we would otherwise need to pull repeatedly if we did not account for geographic proximity.
Isochrone generation is run per executor, per reference point, using a cached Valhalla Actor.
This generates isochrone polygons at fixed bands, currently configured to:
2, 4, 6, 8, ..., 30 minutes
Each contour is compared with local H3 tiles in OVERLAP mode. Any tile that overlaps an isochrone at any point is assigned the minimum drive-time band it touches. In our use-case, we would rather overinclude than underinclude.
We felt it was more reasonable to slightly overestimate the H3 mapping rather than underestimate it. The travel-time difference across a single H3 cell at resolution 8 is typically small enough to be an acceptable margin of error for this use case.
This choice means that an object near the edge of a cell may occasionally be included even if its exact position lies just beyond the contour. In exchange, the system avoids false exclusions caused by requiring an entire cell to be contained within the contour.
Scaling
We previously used the Spark driver to pull Valhalla tiles for executors, which accessed those tiles through memory mapping.
With particularly large regions and skewed partitions, this architecture is both a Spark antipattern and can become flaky at scale. Network egress required from the driver can cause it to skip heartbeats, resulting in executors being decommissioned and jobs failing.
When scaling up, we instead distributed the .tar download directly to executors. This allows executors to scale independently and can turn a long, unstable job into a short, stable one, at the cost of additional executor resources and network overhead.
Future optimizations could include:
- Splitting and serving Valhalla tiles individually
- Downloading only the tiles required by each geographic partition
- Persisting tiles on executor-local disks
- Hosting tiles in shared memory
- Using a dedicated tile-serving layer
- Reusing cached artifacts across jobs
Ideally, the driver should be completely decoupled from the layer serving routing tiles. Given our specific workloads and scaling needs, the naive .tar download worked well enough.
Query Time
Returning to the type of query we are trying to support:
“Find objects within a specified driving time of point collection A and not within that driving time of point collection B.”
Assume we already have a candidate set of objects. We must filter that set to those that:
- Are within the selected driving-time range of collection A.
- Are not within the selected driving-time range of collection B.
We know:
- Which objects are associated with which H3 tiles.
- Which H3 tiles are within the selected drive-time range of each reference-point collection.
A driving-time range becomes a simple filter:
drive_time_min <= requested_range
The query can therefore be collapsed into a chain of set operations and search_arounds:
A_tiles = tiles where:
point_collection = A
and drive_time_min <= requested_range
B_tiles = tiles where:
point_collection = B
and drive_time_min <= requested_range
result_tiles = A_tiles - B_tiles
result_objects = candidate_objects intersect objects_in(result_tiles)
No route calculation is required at query time. The expensive work, generating contours and mapping them to H3 cell, has already been completed.
The resulting online workflow consists primarily of:
- Numeric filtering
- Object links
- Tile-based joins
- Set intersection
- Set difference
This makes it possible to serve map-accurate driving-time catchments from a fixed set of points quickly and at high scale, while keeping query-time overhead low.
The same precomputed structure can also be reused for:
- Catchment visualization
- Coverage analysis
- Overlap analysis
- Gap analysis
- Proximity filtering
- Comparing multiple point collections
- Determining whether arbitrary spatially associated objects lie within a selected drive-time area
As a bonus, it also makes for very pretty maps:
