OSMLR is designed to provide persistent and (mostly) stable identifiers that represent a section or segment of a road or path. The OSMLR introduction document describes the general premise of OSMLR and how segments are defined. This document describes the strategy and process for updating OSMLR.
The OSMLR process (as does the OSMLR creation process) relies on Valhalla libraries and data. This provides a "routing graph" from which intersections and sections of road between intersections can easily be derived. Valhalla includes a process to "associate" or match OSMLR Ids and segment definitions to Valhalla edges (or portions of edges). This association can be performed multiple times against an existing OSMLR definition as the underying map data is updated. The association process matches OSMLR segments to roads within specific tolerances. These tolerances include how closely the OSMLR Location Reference Points (LRP) match to Valhalla edges and intersections. It also includes tolerances for how closely headings match at LRPs and how closely lengths of the road segment between LRPs match the OSMLR segment definition. Usually the road network data changes slowly (especially on more established, higher classification roads) and the large majority of OSMLR segments properly match the updated Valhalla road graph data. However, some data updates will force existing segments to be deprecated/deleted as the changes result in no matching roads to be found within tolerance of the OSMLR segment. These deleted segments may result in new, replacement OSMLR segments with unique Ids. Also, data updates may represent newly constructed roads (or newly added to the base data) which require new OSMLR segments.
Tolerances used when associating OSMLR segments to Valhalla road segments include:
- Distance from the LRP. This is the distance intersections (nodes) with the routing graph must be from the LRP or distance from the LRP to the closest point along the road segment if the LRP is not placed at an intersection. The default is 20 meters.
- Heading / bearing. This is the difference between the bearing specified for the OSMLR segment and the bearing computed for the road segment. The default tolerance is 15 degrees.
- Length. The length tolerance is the difference in length between the OSMLR segment and the road segment. The default is 20 meters. We are experimenting with a variable tolerance based on the lenght of the OSMLR segment.
- Road classification. The road classification may change slightly properly associate OSMLR to the road segment. As long as the classification does not change the Valhalla hierarchy (tile level) the association remains valid. Examples are changes betweem motorway, trunk, or primary and changes between secondary and tertiary. Examples that no longer can be associated are changes between secondary and primary or between unclassified and tertiary.
OSMLR segments are immutable. While underlying data changes, as long as the roads match the OSMLR segments within specific tolerances the OSMLR segment remains valid. Properties of the OSMLR segment do NOT get updated. This decision has positives and negatives:
-
On the plus side this protects against a segment "drifting" through time such that each successive version matches (within tolerance) the prior version, but may not match earlier versions.
-
On the negative side segment lengths can change slightly leading to slight inaccuracies in average speed computations of any data matched against the segment.
By preserving matched segments, there is no provision to merge segments in cases where underlying data might be changed such that two adjoining segments can be merged (for example when an intersecting road along the segment is deleted). This helps conserve Ids (rate of new Ids grows more slowly) and keeps previously associated data without special update processing. However, in the case of short OSMLR segments it could be desirable to merge them into other segments where possible.
At present, the OSMLR build process assigns whatever IDs it sees fit to the segments it creates. This works well for one-off builds, but presents a problem when there is an installed base of users in a centralized system. For example, if we versioned the IDs then the segment with ID 0/1/1 generated in 2017Q1 would be called 2017Q1:0/1/1 or similar (probably more efficiently bit-packed, but that's irrelevant to the point). This means that anyone slow to update to new data would be sending old IDs, which the central system would have to either translate to the new IDs or drop the data. Dropping the data is obviously bad, and translating might be non-trivial. At the very least, translating would require us to keep a translation table whose size would grow with the number of OSMLR data releases.
Instead, we propose maintaining a single ID "namespace", so that 0/1/1 would always refer to the same segment so long as that segment didn't dramatically change. This requires the OSMLR generation process to begin by matching the previous segment descriptors against the current data, and keeping the IDs for those which continue to match. Since OSMLR descriptors are designed to be tolerant to some kinds of changes, we anticipate that the majority will continue to match. The few which do not match will result in the old IDs being marked as "deleted" or "superseded" and new IDs being allocated for the new segments (possibly with forward / back references to aid in translation).
The OSMLR generation process (osmlr) has been updated to accept an optional OSMLR pbf directory. This indicates that the OSMLR generation process should apply updates based on the supplied OSMLR segment definitions. This triggers the segment "migration" process rather than creating an initial or new set of OSMLR segments.
When updating or migrating OSMLR segments, the Valhalla data used by OSMLR generation must be "traffic-enabled". This means it must have OSMLR segment associations present in the Valhalla tiles (populated by running the valhalla_associate_segments process when creating Valhalla data). For new OSMLR segment generation the Valhalla tiles must not contain OSMLR segment associations.
The OSMLR segment migration process essentially compares OSMLR segment definitions to Valhalla OSMLR association information to determine OSMLR segments that are still valid (have not changed significantly) and those that must be replaced. New segments are created both to replace OSMLR segments that have significant change as well as create new segments caused by new data (e.g. new roads).
The OSMLR segment migration process proceeds as follows:
- Iterate through OSMLR tiles (protocol buffer).
- Copy all existing OSMLR segments to the new tile.
- Identify all OSMLR segments that are associated to the Valhalla routing data. These segments are still valid and remain unchanged with their existing index within the tile remaining unchanged (OSMLR segments are immutable). Skip any previously deprecated OSMLR segments. What remains is the set of OSMLR segments that must be deprecated (they no longer associate to the routing data within specific tolerances). These segments are marked as deprecated/deleted with the date added to specify when the OSMLR segment was deprecated.
- The OSMLR "creation" process is then run to generate new segments that either replace deprecated segments (if applicable) or identify newly added roads within the data. When creating new segments, any road segment that is already associated to an OSMLR is skipped / disallowed. New segments get sequential Ids within the tile, following all currently existing Ids so there is no collision of Ids within the tile. The new segments also have the date indicating when the segment was added to the OSMLR tile.
As the protocol buffer output is updated, the GeoJSON output is similarly updated by removing the "deleted" or "superseded" features from the featurecollection. New features are appended to the existing feature collection for existing GeoJSON tiles.
The OSMLR update process tries to maintain existing OSMLR segments, where possible, under minor data edits and changes to the underying roads structure. However, certain changes require replacement of existing OSMLR segments. This section describes some common changes and how OSMLR segments are handled under these conditions.
- Editing/adjustment of intersections. If the end nodes of the OSMLR segment (positions of the intersecting ways at the end of the segment) remain consistent (same intersection) and the length remains within some threshold the existing OSMLR segment remains unchanged.
- Change of Segment Length. When associating road segments to OSMLR segments, the length of road between Location Reference Points must match within a specified tolerance. This tolerance allows for modes changes to the underlying shape of the road segment and points representing the shape of the roadway. Length of the associated segment changes outside some threshold. Do we replace the segment with a new segment? Since we use length from the OSMLR segments within the Datastore to compute average speeds from the histogram durations (elapsed time) this means that if the length changes significantly then the average speed computations can be inaccurate for historical data imports. If the OSMLR segment length exceeds the max (1km) then we may want to split the segment (realistically how drastically could the length change?)
- Reclassification (changing highway tags). If the reclassification results in the edge remaining in the same tile (same hierarchy) then the same Id can be re-used. Otherwise the OSMLR segment must be replaced / superseded.
- Inserting an intersecting way along the segment. Approach depends on whether the intersection can be “merged” (e.g. adding a “local” road along a primary road) or whether the intersection forces the segment to be split. If the intersection can be merged then the existing segment remains. Otherwise, the old segment is deprecated and 2 new segments are created.
- Reclassification of intersecting roads at segment ends. This generally will not require changes unless the intersecting roads are “downgraded” such that the segment can be merged across the segment end node. Even in this case the segment can remain, even if it could be expanded / merged across the intersection.
- Deleted roads that now allow merging segments. When an intersecting road is removed (or reclassified) such that OSMLR segments can be merged, do we want to merge the segment or preserve the prior? Preserving prior segments leads to less churn / change of OSMLR Ids so we are favoring the approach that does not merge in this case unless and until other changes cause the original OSMLR segments to be otherwise invalidated.