map matching returns name for the wrong direction

[mortada]

Using the v5.5.4 release, I notice that map matching can map a trace to the wrong direction. Here is a small example that reproduces the problem.

Given the following trace/query, which goes from west to east:

/match/v1/car/-120.147778,34.392861;-120.147695,34.392889?annotations=true&overview=false

and the following OSM:

<osm generator="test" version="0.6">
<node id="1" lon="-120.1467783" lat="34.3932086" version="1" changeset="1" timestamp="2017-01-19T18:37:02Z" />
<node id="2" lon="-120.147782" lat="34.39286" version="1" changeset="1" timestamp="2017-01-19T18:37:02Z" />
<way id="1" version="1" changeset="1" timestamp="2017-01-19T18:37:29Z">
<nd ref="1" />
<nd ref="2" />
<tag k="highway" v="secondary" />
<tag k="oneway" v="yes" />
<tag k="name" v="westbound" />
</way>
<way id="2" version="1" changeset="1" timestamp="2017-01-19T18:37:29Z">
<nd ref="2" />
<nd ref="1" />
<tag k="highway" v="secondary" />
<tag k="oneway" v="yes" />
<tag k="name" v="eastbound" />
</way>
</osm>

the resulting matched name is the wrong direction (westbound)

{"tracepoints":[{"location":[-120.147778,34.392861],"hint":"AAAAAAEAAIAEAAAAUQAAAAEAAAAAAAAAAAAAAAAAAAABAACAvrDW-B3LDAK-sNb4HcsMAgAAAQF_0OeL","matchings_index":0,"waypoint_index":0,"name":"westbound"},{"location":[-120.147695,34.392889],"hint":"AAAAAAEAAIAEAAAASgAAAAgAAAAAAAAAAAAAAAAAAAABAACAEbHW-DnLDAIRsdb4OcsMAgAAAQF_0OeL","matchings_index":0,"waypoint_index":1,"name":"westbound"}],"matchings":[{"distance":8.2,"duration":0.7,"legs":[{"distance":8.2,"steps":[],"duration":0.7,"annotation":{"nodes":[2,1],"datasources":[0],"duration":[7.4],"distance":[8.22993]},"summary":""}],"confidence":0.980289}],"code":"Ok"}

Note that my OSM is such that both ways share the same nodes. I remember seeing this same problem in v4.x and it was fixed in v4.x. But this does not seem to work in v5.x.

I'd like to be upgrade from v4 to v5 and any help would be appreciate. Thanks

[danpat]

@mortada The most likely cause is that OSRM (still) doesn't support different names in different directions on a way, only one name gets baked into the data structures at pre-processing time, and which one you get is basically random.

This PR: #2298 implementes this for OSRMv5 this feature for OSRMv4, but it hasn't been updated to OSRM v5 at this stage. EDIT: correction - this patch is against v5, it shouldn't require too much work to bring up-to-date if someone wants to tackle it.

The main reason this isn't implemented in the mainline is that it adds significant memory overhead (4 bytes per edge-based-node, so about 4-8GB for the planet), and it only affects a tiny number of ways in OpenStreetMap (about 40 roads in total, globally).

Global instances of the name:forward and name:backward properties on ways, generally, OSM discourages ways sharing multiple nodes, preferring :forward and :backward properties on a single way.

Something like this is definitely asking for a sparse data optimization (i.e. a separate lookup table for bidirectionally named roads, resolved at unpacking time).

[danpat]

I'll also note, there are about 2180 instances of name:left/right on highway=*-tagged ways - these are also a candidate for this "two names on a single edge" behaviour. They primarily exist on admin area boundaries (24k instances), but there are a few on roads too.

[mortada]

@danpat is there a reliable way to get the map matcher to return whether a trace is traversing in the forward or backward direction of the matched edge?

[danpat]

@mortada you can pass the the annotations=true parameter as part of the request, and you'll get the node IDs of the traced route, in the traversed order. You could use these to determine the traversal direction.

See the documentation at http://project-osrm.org/docs/v5.5.4/api/#match-service and the structure of the annotations response at http://project-osrm.org/docs/v5.5.4/api/#annotation-object

[sjones94549]

Thanks @danpat -- we're planning to use annotations for now, but were hoping to avoid the big node join if possible. It is a shame to lose data, but understood that the typical use case has very few impacted ways (ours happens to have many).

[danpat]

@sjones94549 as a very quick-and-dirty hack, you could try encoding the first node ID value as part of the way name. If that value doesn't match the first value in the annotation node ID sequence, you know you've traversed it in reverse.

It's a fugly hack, but I think it'll work.

[sjones94549]

@danpat aren't the annotation node IDs a segment that may be somewhere in the middle of a long edge? How would one tie those segment IDs to an original OSM way without knowing the original node chain?

[danpat]

@sjones94549 hmm, good point. It'll work for traces that cross the beginning of ways, but yeah, it won't work for traces that are only on a sub-section of a longer un-broken way.

To do this inside OSRM, I really see two options:

• forward-porting enable reverse name IDs #2298
• or exposing a forward/reverse flag as an annotation, and encoding both the forward/reverse name in your way.

Both of these will require some C++ work to implement.

[Komzpa]

Can this be also done by mapping the road as two separate in space one-ways?
Similar to this: http://www.openstreetmap.org/#map=19/59.94014/30.27879

[sjones94549]

possibly if we offset the endpoint nodes of these ways they'd make it through contract without getting lost, but a cleaner solution would be preferable :P

[sjones94549]

@danpat I'm curious if you've seen osrm-extract take a long time during the Sorting edges by renumbered start phase with long names. I have a California region that takes ~10 minutes to run through osrm-extract with 8-character names, and overnight with up to 254-character names. This is with 128 cores, 2T RAM, and everything done in-memory. There may be more to it than name length, since this map has long ways broken into shorter ways, but it is interesting that turning the name-length knob matters so much.

These long names are related to this ticket. I'm packing (forward way ID, reverse way ID, [node IDs]) into the name field. This works great on smaller regions, like Delaware, but takes prohibitively long in bigger regions.

As an aside, I ran into two string length thresholds when trying this. First, osmium raises an exception at 1024 characters, and will simply reject any OSM or PBF with longer values when parsing. Second, OSRM silently truncates to ~254 characters (RangeTable limit, I believe). I see #3585 from 2 days ago might bump this up, but ideally it'd also warn when truncating. In any case, I'll try the new names table and see what happens.

[daniel-j-h]

As an aside, I ran into two string length thresholds when trying this. First, osmium raises an exception at 1024 characters, and will simply reject any OSM or PBF with longer values when parsing. Second, OSRM silently truncates to ~254 characters (RangeTable limit, I believe). I see #3585 from 2 days ago might bump this up, but ideally it'd also warn when truncating. In any case, I'll try the new names table and see what happens.

Strings in OSM can only have a maximum length of 256 unicode characters. See #2844.
The changes to the range table only up the limit from 256 bytes to 256 unicode codepoints.

[danpat]

@sjones94549 The sorting step that it's holding up on does perform a lexicographical comparison of the names (to determine the sort order). If the strings are long and similar looking, this could be a big source of the slowdown. There are lots of these comparisons done.

The comparison done to sort edges is done here, it looks like you're triggering the final std::lexicographical_compare test, which is quite expensive (and is avoided when the names the same, which they often are for normal OSM maps):

osrm-backend/src/extractor/extraction_containers.cpp

Line 66 in 6e1c4bf

struct CmpEdgeByInternalSourceTargetAndName

[oxidase]

The final std::lexicographical_compare is aimed to solve #2617 via #2624 to prevent spurious name changes in guidance. It is extremely inefficient because it make edge soring sequential if hit to guarantee exclusive access to the stxxl vector cache as in #3033.

[mortada]

@oxidase in my use case the graph is actually structured such that each way has a unique name. would it be possible to make it skip this inefficient sort?

[oxidase]

The problem is not in non-unique names in ways, but in non-unique ways that share the same nodes. Say there are four nodes "a b c d" and two ways "abcd" and "bcd". With the check all three segments ab, bc, cd always will have the name "abcd". Without the check the first segment will be always "abcd", but the second and the third will be either "abcd" or "bcd" depending on edges processing order and the result with collapsed names will be one of {"abcd", "abcd,bcd", "abcd,bcd,abcd"}.

It is possible to compare only name ids that is cheap as comparing node ids, but there is also no fixed ordering in name ids, so one of {"abcd", "abcd,bcd"} result will be possible.

Also it will not fix the original problem: the rtree contains only "westbound" edge and "eastbound" edge is not included into edge-based graph because of filtering. With removed filtering http 'localhost:5000/match/v1/car/-120.147778,34.392861;-120.147695,34.392889?annotations=true&overview=false' gives

``` { "code": "Ok", "matchings": [ { "confidence": 0.973725, "distance": 8.2, "duration": 0.7, "legs": [ { "annotation": { "datasources": [ 0 ], "distance": [ 8.188221 ], "duration": [ 0.7 ], "nodes": [ 2, 1 ], "weight": [ 0.7 ] }, "distance": 8.2, "duration": 0.7, "steps": [], "summary": "", "weight": 0.7 } ], "weight": 0.7, "weight_name": "duration" } ], "tracepoints": [ { "hint": "AQAAgAAAAAAIAAAAAAAAAFIAAAAAAAAAAAAAAAAAAABSAAAAAAAAAAAAAAABAAAAAQAAgL6w1vgdywwCvrDW-B3LDAIAAAEBWhICqw==", "location": [ -120.147778, 34.392861 ], "matchings_index": 0, "name": "eastbound", "waypoint_index": 0 }, { "hint": "AQAAgAAAAAAIAAAABwAAAEsAAAAAAAAAAAAAAAcAAABLAAAAAAAAAAAAAAABAAAAAQAAgBCx1vg6ywwCEbHW-DnLDAIAAAEBWhICqw==", "location": [ -120.147696, 34.39289 ], "matchings_index": 0, "name": "eastbound", "waypoint_index": 1 } ] } ```

/cc @TheMarex

[mortada]

@oxidase in my use case the road network is such that two ways in the form of "abcd" and "bcd" would never happen. These two ways would be "ab" and "bcd". The only node sharing in my case would be having an identical but reversed list of nodes (i.e. "abcd" and "dcba")

would it be possible to make this sort optional?

[oxidase]

@mortada sure, you can try it locally, but i guess making the lexicographical sort optional will not help, because it should not hit.

The "eastbound" edge can not snapped in matching because the "eastbound" edge does not exists as an edge-based node in the graph due to filtering out here

osrm-backend/src/extractor/edge_based_graph_factory.cpp

Lines 282 to 287 in 2b00d92

	if (node_u > node_v)
	{
	continue;
	}
	BOOST_ASSERT(node_u < node_v);

[sjones94549]

While isolating a potential issue trying to get this name bit working (match annotations nodes orders reversed on for coordinates that project near way nodes), I came up with an oddball. Here, I have two coordinates supplied to match, but it returns three nodes (and the first two are indeed in reverse order). I expected "nodes":[2,3], but got "nodes":[3,2,3]. Is this expected? (waypoints basically match to node 3)

<osm generator="sjones94549" version="0.6">
    <node id="2" lon="-122.112486" lat="37.439013" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />
    <node id="5" lon="-122.1130085" lat="37.4395136" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />
    <node id="4" lon="-122.1128925" lat="37.4394027" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />
    <node id="7" lon="-122.113625" lat="37.440103" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />
    <node id="6" lon="-122.1134532" lat="37.4399388" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />
    <node id="1" lon="-122.1123676" lat="37.4389004" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />
    <node id="3" lon="-122.112646" lat="37.439167" version="1" changeset="1" timestamp="2017-02-28T20:00:06Z" />

    <way id="1" version="1" changeset="1" timestamp="2017-02-28T20:00:22Z">
        <nd ref="1" />
        <nd ref="2" />
        <nd ref="3" />
        <nd ref="4" />
        <nd ref="5" />
        <nd ref="6" />
        <nd ref="7" />
        <tag k="highway" v="trunk" />
        <tag k="oneway" v="yes" />
    </way>
</osm>

http://localhost:5000/match/v1/car/-122.112725,37.439102;-122.112739,37.439115?annotations=true&overview=false

{
    "code":"Ok",
    "matchings":[
        {
            "confidence":0,
            "legs":[
                {
                    "annotation":{
                        "datasources":[0,0],
                        "nodes":[3,2,3],
                        "duration":[1.8,1.2],
                        "distance":[22.119263,22.119263]
                    },
                    "summary":"",
                    "duration":3,
                    "steps":[],
                    "distance":44.2
                }
            ],
            "duration":3,
            "distance":44.2
        }
    ],
    "tracepoints":[
        {
            "waypoint_index":0,
            "matchings_index":0,
            "hint":"AAAAgP___38AAAAAAAAAABIAAAAVAAAANgAAAAAAAAABAACAerW4-L5GOwIrtbj4fkY7AgIAAQEAAAAA",
            "name":"",
            "location":[-122.112646,37.439166]
        },
        {
            "waypoint_index":1,
            "matchings_index":0,
            "hint":"AAAAgP___38AAAAADAAAAAwAAAAJAAAASAAAAAAAAAABAACAerW4-L5GOwIdtbj4i0Y7AgEAAQEAAAAA",
            "name":"",
            "location":[-122.112646,37.439166]
        }
    ]
}

Here's what those two coordinates look like next to the complete way:

Zoomed in a bit:

[TheMarex]

@sjones94549 yes that looks like a bug. Broke this out into #3775