Looking for a trajectory similarity measure

Question

For my final academic work I have developed a compression algorithm for GPS trajectories. I can estimate the quality of the spatio-temporal compression by computing the syncronized euclidean distance (SED) between the compressed and the original trajectory and evaluate my algorithm's performance against a well-known compression algorithm.

A spatio-temporal algorithm, like mine, reduces the trajectory trying to maintain as much temporal information as possible. Spatial algorithms (e.g. Douglas-Peucker algorithm) realize the compression referring only to the spatial characteristics.

What happens now? Considering a spatio-temporal aspect, my algorithm is better than DP. I can assure this by SED measurements. If I plot the three trajectories (original, mine and DP compressed), the trajectory compressed with DP has a better fitting with the original trajectory. The eye-only measurements don't satisfy my need: I need, indeed, an error metric that numerically demonstrates how the DP algorithm is better than mine in a spatial manner.

So I could write: "Referring to the spatio-temporal factor, my algorithm is better than DP, because it has an SED factor less than DP's SED factor. Alas, simple spatial factor awards DP algorithm because its (name of the new metric) is better than mine".

I have been thinking of perpendicular euclidean distance, but I really don't know if this could be useful. Dynamic Time Warping? What metric could I use for this?

Answer 1

I think you might be best off considering whether you should use a range of metrics. Some users may consider the average spatialite error to be of concern, but a bigger concern is "how bad does it get". You are presumably looking at this in at least some respect (e.g. temporal vs spatial), I'm just suggesting looking very widely.

I don't have all the metrics that might be used, but one you should look at is the Hausdorff distance. There is an implementation in GEOS (and presumably in JTS). We also support it in SpatiaLite and its in PostGIS too, if you'd prefer to use that.