Mobility and Uncertainty - Mobility Data - page 98

1 . The closest n road segment receives
weight 1. Notice then that the road segments to be included are computed
using space-time prisms. A score for a segment s is computed adding up the
weights of all the segments that match s .
3. Finally, compute, within this limited network, the k -shortest paths, taking the
shortest path with the highest score computed in Step 2.

the second closest receives weight n −

Chapter 2 studied geometric map-matching algorithms. These algorithms
are efficient due to their simplicity. On the other hand, geometric algorithms
have some drawbacks that sometimes prevent trajectory reconstruction. This
is the case, for instance, when observations are taken at irregular intervals, or
there are large gaps in the data (this may occur, for example, when an object
enters a large tunnel, preventing signal reception). In these cases, we need
more sophisticated algorithms, such as the one described above. Summarizing
experiments performed on real-world data showed the following:

ST-MM is sensitive to the maximum speed. For relatively high speeds (70-
120 km/h) it is stable and delivers good performance, with an average of
around eighty percent trajectory reconstruction rate. When speeds are lower,
performance decreases as well as the reconstruction rate.
Geometric algorithms perform well when data are recorded at regular inter-
vals and there are not large gaps between observations (note that these algo-
rithms are independent of the maximum speed).
When data are irregular and contain large gaps, ST-MM delivers better recon-
struction rates, except when maximum speeds are low. In the latter case, geo-
metric algorithms are more efficient, although reconstruction rates remain
low for both algorithms.
The scenario where ST-MM is clearly better than simple geometric algo-
rithms is the one in which speeds are relatively high and measures are taken
at irregular intervals. On the contrary, where speeds are low, geometric algo-
rithms perform better because the prisms in ST-MM include a high number
of roads, decreasing performance.

5.3.5 Trajectory Clustering and Uncertainty

Clustering is a data mining technique that partitions a data set into collections
of data objects, such that within each partition the objects are “similar” to
each other and “different” from the objects contained in other partitions. In the
context of moving object data, the clustering technique aims at identifying
groups of objects that follow similar trajectories. Clustering is tackled in detail in
Chapter 6 of this topic. In this section we show how the presence of uncertainty
impacts on clustering results.