Error in `fmm': double free or corruption (out)

[almenea]

I tried to run fmm with city scale graph and one gps trajectory. I ended up with memory corruption.

root@81df69e51c95:/fmm# fmm fmm-config/fmm_config.xml
------------ Fast map matching (FMM) ------------
------------     Author: Can Yang    ------------
------------   Version: 2018.03.09   ------------
------------     Applicaton: fmm     ------------
Validating configuration for map match application:
    Warning, overwrite existing result file.fmm-output/mr.txt
Validating success.
------------------------------------------
Configuration parameters for map matching application:
    Network_file:       data/street_network/edges/edges.shp
    Network id:         osmid
    Network source:     from
    Network target:     to
    ubodt_file:         fmm-output/ubodt.txt
    multiplier:         49966
    nhash:              11311
    delta:              5000
    ubodt format(1 binary, 0 csv): 0
    gps_file:           data/trips/trips.shp
    gps_id:             id
    k:                  4
    radius:             0.01
    gps_error:          0.001
    penalty_factor:     0
    result_file:        fmm-output/mr.txt
    geometry mode:      2(0 no geometry, 1 wkb, 2 wkt)
------------------------------------------
Read network shp file from data/street_network/edges/edges.shp
Id column osmid
    Number of edges in file: 76108
    SHP ID idx: 11
    SHP source idx: 2
    SHP target idx: 14
    Geometry type is Line String
    SRID is 4326
Read network finish.
    The maximum node ID is 2039118004
    Total number of edges read 76108
Start to construct boost rtree
Finish construct boost rtree
Reading UBODT file (CSV format) from: fmm-output/ubodt.txt
    Header line skipped.
Read rows: 1000000
    Number of rows read 1627795
    Estimated load factor #elements/#tablebuckets 5425.98
    *** Warning, load factor is too large.
Finish reading UBODT.
Reading meta data of GPS trajectories from: data/trips/trips.shp
    Index of ID column: 0
    Total number of trajectories: 1
Finish reading meta data
Write result to file: fmm-output/mr.txt
Start to map match trajectories with total number 1
Progress 0 / 1

=============================
MM process finished
Time takes 2.071
Time takes excluding input 0.006
Finish map match total points 136 and points matched 0
Matched percentage: 0
Point match speed:0pt/s
Point match speed (excluding input): 0pt/s
Clean UBODT
*** Error in `fmm': double free or corruption (out): 0x0000000001804610 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f85583917e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7f855839a37a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f855839e53c]
fmm[0x409c9e]
fmm[0x4058cd]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f855833a830]
fmm[0x4066e9]
======= Memory map: ========
00400000-00436000 r-xp 00000000 08:01 1740679                            /root/bin/fmm
00635000-00636000 r--p 00035000 08:01 1740679                            /root/bin/fmm
00636000-00637000 rw-p 00036000 08:01 1740679                            /root/bin/fmm
00cc0000-062bd000 rw-p 00000000 00:00 0                                  [heap]
7f8540000000-7f8540021000 rw-p 00000000 00:00 0
...
Aborted

I generated the network using osmnx:

location_point = (24.6946907, 46.72079802)
city = ox.graph_from_point(location_point, distance=10000)
ox.save_graph_shapefile(city, filename='street_network')

GPS as WKT (generated using GeoPandas):

'LINESTRING (46.64934397 24.73307848, 46.64477348 24.7419405, 46.64470911 24.74213362, 46.64129734 24.74874258, 46.64112568 24.74918246, 46.64093256 24.74953651, 46.63610458 24.76218581, 46.63799286 24.76747513, 46.64007425 24.77189541, 46.64063215 24.77313995, 46.64082527 24.77354765, 46.64101839 24.77396607, 46.64119005 24.77436304, 46.64241314 24.7773993, 46.64234877 24.77742076, 46.64224148 24.77733493, 46.63973093 24.77704525, 46.63960218 24.77693796, 46.63958073 24.77692723, 46.63174868 24.79223728, 46.63170576 24.79221582, 46.63170576 24.7922051, 46.63170576 24.79221582, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.6316843 24.7922051, 46.6316843 24.7922051, 46.6316843 24.7922051, 46.6316843 24.7922051, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79218364, 46.63166285 24.79218364, 46.63166285 24.79218364, 46.63166285 24.79218364, 46.6316843 24.79230165, 46.6316843 24.79236603, 46.6316843 24.79237676, 46.6316843 24.79241967, 46.6316843 24.79244113, 46.6316843 24.79245186, 46.6316843 24.79244113, 46.6316843 24.79244113, 46.6316843 24.79244113, 46.6316843 24.79244113, 46.6316843 24.79245186, 46.6316843 24.79245186, 46.63164139 24.79249477, 46.63164139 24.79252696, 46.63159847 24.79254842, 46.63159847 24.79260206, 46.63157701 24.79265571, 46.63155556 24.79273081, 46.6315341 24.79278445, 46.63078308 24.7942543, 46.63258553 24.79436159, 46.63331509 24.79476929, 46.63352966 24.79485512, 46.63352966 24.79485512, 46.63374424 24.79495168, 46.63374424 24.79495168, 46.63395882 24.79503751, 46.63395882 24.79504824, 46.63417339 24.79513407, 46.63417339 24.7951448, 46.63436651 24.79523063, 46.63438797 24.79523063, 46.63458109 24.79531646, 46.63460255 24.79532719, 46.63479567 24.79541302, 46.63481712 24.79542375, 46.63501024 24.79549885, 46.63522482 24.79559541, 46.63503170000001 24.79552031, 46.63524628 24.79560614, 46.6354394 24.79569197, 46.63546085 24.7957027, 46.63565397 24.7957778, 46.63567543 24.79579926, 46.63329363 24.79504824, 46.63331509 24.79500532, 46.63333654 24.79498386, 46.633358 24.79497313, 46.633358 24.79496241, 46.633358 24.79496241, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.63337946 24.79495168, 46.63337946 24.79495168, 46.63342237 24.79495168, 46.63361549 24.79502678, 46.63365841 24.79504824, 46.63370132 24.79505897, 46.63372278 24.79506969, 46.6337657 24.79509115, 46.63380861 24.79510188, 46.63129807 24.80053067, 46.63116932 24.80078816, 46.63116932 24.80079889, 46.63101912 24.80105639, 46.63065434 24.80177522, 46.63050413 24.80204344, 46.63037539 24.80231166, 46.63022518 24.80257988, 46.63009644 24.8028481, 46.63007498 24.80286956, 46.62994623 24.80310559, 46.62981749 24.80337381, 46.62979603 24.80359912, 46.62962437 24.80404973, 46.62955999 24.80416775, 46.62951708 24.80427504, 46.62945271 24.80439305, 46.62936687 24.80451107, 46.6293025 24.80463982, 46.62923813 24.80477929, 46.62917376 24.80489731, 46.62827253 24.80658174)'

[cyang-kth]

@Almenea I also encountered the same problem. It will check it and reply to you later.

[cyang-kth]

Hi, Almenea

I found the cause of this problem. The node id in the shapefile generated by osmnx is too big (as you can see in your warning with maximum node id of 2039118004), which exceeds the range of an integer type after multiplied with nhash. Therefore, it causes problem in freeing the UBODT.

To avoid that problem, one way is to assign a new id to each node.

1. add an extra column in the nodes.shp file using the feature index, which constrains the range to be within 60,000 (varying with the number of nodes).
2. Join the edges.shp file with the new node file to add two extra columns fid and tid which replaces the old from and to column with a much smaller integer value.
3. Rerun the two program ubodt_gen and fmm.

[cyang-kth]

After limiting the range of node ID, the result still shows that 0 points are matched. I think it is caused by some complicated network infrastructure. I will check later.

Besides, the network you generated is too small to cover the trajectory as shown below. You should try 15000 instead of 10000.

[cyang-kth]

The problem of no points matched to the road network is caused by a specific noise (move back behavior) in the GPS data, which cannot be handled correctly by the current algorithm.

Moving in a reverse direction on a single directional road edge is not allowed by the program but it exists in your data due to noise as shown below.

I tried to remove these noise by simplying the trajectory using Douglas Peucker Algorithm (10meter), to generate a sparser trajectory containing 18 points (orange color below). I also increased the size of UBODT to 0.03 (=3000m). Now the trajectory can be successfully matched. (blue color is the map matched trajectory)

If you do not increase the delta of UBODT, the trajectory may still be unmatched because some points are far away (more than 2 km) after simplication. More advanced line simplication algorithm should be tried here to keep the trajectory dense and remove some noisy observations.

[almenea]

Yes, you are right. The trajectory falls outside the map. I tried to use Ramer-Douglas-Peucker algorithm to simplify the trajectory and fmm started working as expected. Thank you for your efforts.