Efficient Greedy Discrete Subtrajectory Clustering

We cluster a set of trajectories T using subtrajectories of T. Clustering quality may be measured by the number of clusters, the number of vertices of T that are absent from the clustering, and by the Fr'echet distance between subtrajectories in a cluster. A Delta-cluster of T is a cluster P of subtrajectories of T with a centre P ∈ P with complexity ℓ, where all subtrajectories in P have Fr'echet distance at most Delta to P. Buchin, Buchin, Gudmundsson, L"offler and Luo present two O(n2 + n m ℓ)-time algorithms: SC(max, ℓ, Delta, T) computes a single Delta-cluster where P has at least ℓ vertices and maximises the cardinality m of P. SC(m, max, Delta, T) computes a single Delta-cluster where P has cardinality m and maximises the complexity ℓ of P. We use such maximum-cardinality clusters in a greedy clustering algorithm. We provide an efficient implementation of SC(max, ℓ, Delta, T) and SC(m, max, Delta, T) that significantly outperforms previous implementations. We use these functions as a subroutine in a greedy clustering algorithm, which performs well when compared to existing subtrajectory clustering algorithms on real-world data. Finally, we observe that, for fixed Delta and T, these two functions always output a point on the Pareto front of some bivariate function θ(ℓ, m). We design a new algorithm PSC(Delta, T) that in O( n2 log4 n) time computes a 2-approximation of this Pareto front. This yields a broader set of candidate clusters, with comparable quality. We show that using PSC(Delta, T) as a subroutine improves the clustering quality and performance even further.