Performance

Map matching

A case study is reported in the original paper with real world datasets in Stockholm:

• GPS: 644,695 trajectories containing 6,812,720 points
• Road network: 23,921 nodes and 57,928 directed edges
• UBODT size: 4,305,012 rows
• k = 8 (candidate set size), r = 300 meters (search radius)

As reported in the paper, on a desktop with Intel(R) Core(TM) 2 Quad CPU Q9650 @ 3.00GHz (4 processors), the speed of map matching (single processor) is about:

• 25000 points/s (WKB Geometry output, mode 1)
• 45000 points/s (No geometry output, mode 0)

On Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz (8 processors), the speed are reported as:

Program	WKB speed	WKT speed	No geom speed
fmm	52,890	17,905	58,830
fmm_omp	221,797	77,910	289,031

UBODT precomputation

Statistics of ubodt construction on the network of Netherland (700k nodes and 1 million edges) http://geodata.nationaalgeoregister.nl/nwbwegen/extract/nwbwegen.zip

delta (m)	running time	rows	csv size
1000	3min27.5s	19,022,620	766 MB
3000	4min32.9s	79,998,367	3,2GB