Clustering trajectories

Late last year I attended a (great) workshop in the Netherlands organised by Marc van Kreveld. From that workshop a few (!) papers came out. One of them was just accepted to ISAAC - "Detecting Commuting Patterns by Clustering Subtrajectories" by Kevin Buchin, Maike Buchin, Jun Luo, Maarten Löffler and me.

The problem of clustering trajectories is surprisingly hard. In the data mining/database community there are several papers on this problem that are fairly fast but not very accurate (useful?).

In the paper we focus on finding subtrajectories of a single trajectory that forms a cluster (can easily be extended to the general clustering problem). This is useful for detecting, e.g., commuting patterns or seasonal migration behaviour. Our approach builds on the Frechet distance and heavily makes use of the freespace diagram. This gives an accurate definition of a trajectory cluster (imho) but it is very costly to compute (both in time and space). The running time is roughly quadratic (for most settings) and a (non-optimised) implementation can handle 10K points in roughly 20 minutes.

The obvious open problem is: Is there an accurate definition of a trajectory cluster that would allow for a more efficient implementation?