Running map matching using a custom road network (not OSM)

eastcirclek · March 10, 2021, 4:57pm

Hi,

While searching for an open source implementation of the HMM-based map-matching algorithm, I found GraphHopper’s implementation.

We’re not using OSM but a custom road network each line of which looks like

“edge,from_node,to_node,geojson_linestring,one_way,road_category,road_lane”

For example,

“150525009781009783,150525009781,150525009783,LINESTRING(169618 450000,169558 449917),0,9,1”

Are these fields are enough to construct a road network on which I can run GraphHopper’s map-matching implementation?

Best,

easbar · March 11, 2021, 11:13pm

You could convert your data into the OSM format and then use the standard GH OSM import. Mapping your ‘road_category’ to OSM road_class might be the easiest way to go, but you could also use your own FlagEncoder implementation. GraphHopper routing also allows using CustomWeighting that makes it much easier to use your own road categories, but unfortunately this is not supported for map-matching yet. With some Java knowledge this should be possible though.

eastcirclek · May 24, 2021, 7:56am

Hi @easbar,

I’ve studied OSMReader for a while and decided not to convert my data into the OSM format. Instead, I directly import the custom road network into the internal format of GH in order to run GH’s map match.

Considering the following format:

edge,from_node,to_node,geojson_linestring,one_way,road_category,road_lane

What I’ve done is as follows:

from_node and to_node are stored as a tower node via PointAccess::setNode
the coordinates in geojson_linestring are a pillar node and stored via EdgeIteratorState::setWayGeometry
AbstractFlagEncoder’s accessEnc and avgSpeedEnc are configured accordingly using one_way and road_category. I found this is important as it’s used in Weighting::calcEdgeWeightWithAccess.

After importing my custom road network, I ran GH’s map match using a trajectory and I’ve found that MatchResult::getMatchLength matches my expectation.

But GH’s map match takes a very long time and could you give me some advice to achieve a better performance? For a two-hour trip of 105.951km, GH’s map match takes around 50 seconds.

FYI, my network (the entire map of South Korea) being converted to GH is

location index created in 2.0618937s, size:4 642 617, leafs:575 669, precision:300, depth:6, checksum:1653204, entries:[16, 16, 16, 16, 16, 4], entriesPerLeaf:8.0647335
flushing graph car|RAM_STORE|2D|no_turn_cost|5,17,4,4,5, details:edges:3 226 342(99MB), nodes:2 622 258(31MB), name:(1MB), geo:15 392 663(59MB), bounds:124.61939040269314,131.86962521632003,33.17599549541317,38.58458226076817, totalMB:2319, usedMB:1504)

Best,

eastcirclek · May 24, 2021, 8:12am

Here’s a flame graph taken from IntelliJ

easbar · May 24, 2021, 8:54am

Sounds good so far.

Did you try map-matching the same trajectory with unmodified GraphHopper using the OSM map for South Korea? Is it also slow?

How many points are in this trajectory?

eastcirclek · May 24, 2021, 2:40pm

Hey @easbar, the attached is a gpx file I’ve used to test GH’s map matching: east.gpx (341.5 KB)

Did you try map-matching the same trajectory with unmodified GraphHopper using the OSM map for South Korea? Is it also slow?

Your suggestion gives much faster result than my previous attempts using the custom network.

2021-05-24 22:07:11.069 [main] INFO  com.graphhopper.GraphHopper - version 3.0|2021-05-17T02:51:00Z (5,17,4,4,5,7)
2021-05-24 22:07:11.072 [main] INFO  com.graphhopper.GraphHopper - graph car|RAM_STORE|2D|no_turn_cost|5,17,4,4,5, details:edges:1 539 520(47MB), nodes:1 149 086(14MB), name:(4MB), geo:6 843 009(27MB), bounds:121.38442295903913,135.42200666864233,33.114980528838494,43.11188034218282
/Users/east.12/mapmatch/east.gpx
	matches:	285, gps entries:5755
	gpx length:	105749.83 vs 105574.625
	export results to:/Users/east.12/mapmatch/east.gpx.res.gpx
gps import took:0.12338149s, match took: 19.903625

However, as complained in this reddit post, Korea’s OSM is not good as the ones from Korean domestic IT giants like Kakao and Naver in terms of details.

// when importing south-korea-latest.osm.pbf
graph car|RAM_STORE|2D|no_turn_cost|5,17,4,4,5, details:edges:1 539 520(47MB), nodes:1 149 086(14MB), name:(4MB), geo:6 843 009(27MB), bounds:121.38442295903913,135.42200666864233,33.114980528838494,43.11188034218282

// when importing my own data
graph car|RAM_STORE|2D|no_turn_cost|5,17,4,4,5, details:edges:3 226 342(99MB), nodes:2 622 258(31MB), name:(1MB), geo:15 392 663(59MB), bounds:124.61939040269314,131.86962521632003,33.17599549541317,38.58458226076817

eastcirclek · May 24, 2021, 2:48pm

How many points are in this trajectory?

I begin with 5755 coordinates each generated every second. After going through MapMatching::filterObservations, I have 1162 points left.

eastcirclek · May 24, 2021, 3:39pm

I just tried CH when executing OSMReader but it shows a worse performance when map matching:

2021-05-25 00:35:40.449 [main] INFO  c.g.routing.ch.CHPreparationHandler - Creating CH preparations, totalMB:1963, usedMB:215
2021-05-25 00:35:40.458 [main] INFO  com.graphhopper.GraphHopper - version 3.0|2021-05-17T02:51:00Z (5,17,4,4,5,7)
2021-05-25 00:35:40.461 [main] INFO  com.graphhopper.GraphHopper - graph CH|car|RAM_STORE|2D|no_turn_cost|5,17,4,4,5, details:edges:1 539 520(47MB), nodes:1 149 086(14MB), name:(4MB), geo:6 843 009(27MB), bounds:121.38442295903913,135.42200666864233,33.114980528838494,43.11188034218282, CHGraph|car|NODE_BASED, shortcuts:1 215 558 (24MB), nodesCH:1 149 086 (9MB)
/Users/east.12/mapmatch/east.gpx
	matches:	285, gps entries:5755
	gpx length:	105749.83 vs 105574.625
	export results to:/Users/east.12/mapmatch/east.gpx.res.gpx
gps import took:0.11713152s, match took: 21.39495

eastcirclek · May 24, 2021, 3:50pm

I also tried LM but it shows the worst performance in terms of elapsed time among no optimization, CH, and LM:

2021-05-25 00:41:38.345 [main] INFO  c.g.routing.lm.LMPreparationHandler - Creating LM preparations, totalMB:1963, usedMB:184
2021-05-25 00:41:38.404 [main] INFO  c.g.routing.lm.LMPreparationHandler - Finished LM preparation, totalMB:1963, usedMB:260
2021-05-25 00:41:38.408 [main] INFO  com.graphhopper.GraphHopper - version 3.0|2021-05-17T02:51:00Z (5,17,4,4,5,7)
2021-05-25 00:41:38.411 [main] INFO  com.graphhopper.GraphHopper - graph car|RAM_STORE|2D|no_turn_cost|5,17,4,4,5, details:edges:1 539 520(47MB), nodes:1 149 086(14MB), name:(4MB), geo:6 843 009(27MB), bounds:121.38442295903913,135.42200666864233,33.114980528838494,43.11188034218282
/Users/east.12/mapmatch/east.gpx
	matches:	285, gps entries:5755
	gpx length:	105749.83 vs 105574.625
	export results to:/Users/east.12/mapmatch/east.gpx.res.gpx
gps import took:0.10793571s, match took: 24.994724

I might try CH and LM on my custom importer if you didn’t mention trying map-matching using OSM data - thanks a lot for saving my time

Could I expect to achieve a speed up of an order of magnitude so that I can finish map matching trips for two or three hours within a second?

Best,

easbar · May 24, 2021, 4:29pm

So with OSM data (OSMReader) it took 20s and with your own data it took 50s where your own data has about 2.6mio nodes and 3.2mio edges compared to OSM with 1.15mio nodes and 1.5mio edges? That sounds rather reasonable to me. The more edges there are the slower the matching will be.

In my experience CH speeds up map-matching if the data is ‘sparse’ (large distances between the single points), but makes it even slower if the data is ‘dense’. If you generate a coordinate every second and after filtering every fifth point is left that means the average distance between your points is just 5s, so I would not expect CH to speed up the map-matching. For LM it should be faster unless the points are very close(?). Not sure, the best thing you can do is trying it (and of course feel free to share your findings).

Maybe you can do a more aggressive filtering to get rid of more points?

Could you expect such a speed up doing what? Obviously, there is no built-in switch that will automatically give you such a speed-up. I also do not think that there is a quick optimization that makes it that much faster (if there is please make sure to submit a pull request :)). I guess your best chance to speed up the map-matching is filtering out more points so less routes need to be calculated. Off the top of my head one thing that also comes to my mind (if you want to dig a bit deeper) is that you could try to replace the routing algorithm with something like DijkstraOneToMany. The routing algorithms are to some extent optimized for memory usage, but if all you want is fast map-matching you might be able to trade memory vs speed. Another option could be parallelization of some kind (not sure, I never tried). Looking at the flame graph it could also help to pre-calculate/cache all the edge weights of your graph and replace the calcWeight calls with this.

easbar · May 24, 2021, 4:36pm

Now that I thought about it, could you count the number of calcPath calls in MapMatching#computeViterbiSequence when running your example. I’d be interested to know how many path calculations are executed and how long they take on average. It would also help to know the average distance of the calculated paths and maybe even some kind of distribution of the path distances.

eastcirclek · May 25, 2021, 5:46am

@easbar Thanks a lot for the great explanation about what’s going behind scenes when turning on CH and LM.

Maybe you can do a more aggressive filtering to get rid of more points?

I found that MapMatching::measurementErrorSigma is used for not only filtering out observations in MapMatching::filterObservations() but also calculating an envelop to find snaps in MapMatching::findCandidateSnaps(). So increasing measurementErrorSigma makes a negative impact on performance by making more snaps per coordinate.

So I introduce a parameter to replace measurementErrorSignal with which is only used in MapMatching::filterObservations() and change values from 40 to 160 by 20 as follows:

Result of running GH’s map matching on South Korea OSM (with neither CH nor LM)

40 (default) : 20.3 seconds with 1162 observations filtered in
60 : 15.4 seconds with 799 observations filtered in
80 : 10.1 seconds with 615 observations filtered in
100 : 8.7 seconds with 498 observations filtered in
120 : 6.98 seconds with 418 observations filtered in
140 : 6.34 seconds with 359 observations filtered in
160 : 5.14 seconds with 317 observations filtered in

The result is obvious: the numbers are halved when the values have doubled.

eastcirclek · May 25, 2021, 6:33am

Could you expect such a speed up doing what?

We have up to 200 trips finished every second so I thought of launching 200 daemons each capable of performing sub-second map matching upon receiving requests.

I guess your best chance to speed up the map-matching is filtering out more points so less routes need to be calculated.

Yeah, I just found that filtering out observations gives some performance gain as shown above.

Off the top of my head one thing that also comes to my mind (if you want to dig a bit deeper) is that you could try to replace the routing algorithm with something like DijkstraOneToMany. The routing algorithms are to some extent optimized for memory usage, but if all you want is fast map-matching you might be able to trade memory vs speed.

Can I simply replace DijkstraBidirectionRef for DijkstraOneToMany in MapMatching::createRouter()? I just did it, invoked DijkstraOneToMany.calc(int, int) and increasing JVM heap from 2g to 12g on my MBP, but it fails with OutOfMemoryError

Another option could be parallelization of some kind (not sure, I never tried).

It looks not easy for me at this point

Looking at the flame graph it could also help to pre-calculate/cache all the edge weights of your graph and replace the calcWeight calls with this.

Let me spend some time on it. I’ll let you know when I’m done.

easbar · May 26, 2021, 10:38am

No that would not make sense. The idea you could borrow from DijkstraOneToMany is to pre-allocate arrays for the shortest path tree(s) and re-use them for the single searches instead of using a new hash map for every search. This takes more memory but will be faster.