Efficient Greedy Discrete Subtrajectory Clustering

Abstract

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échet distance between subtrajectories in a cluster. A $\hat{I}”$-cluster of T is a cluster $\mathcal{P}$ of subtrajectories of T with a centre $P\in \mathcal{P}$ with complexity $\ell$, where all subtrajectories in $\mathcal{P}$ have Fréchet distance at most $\hat{I}”$ to $P$. Buchin, Buchin, Gudmundsson, Löffler and Luo present two $O(n^2+nm\ell )$-time algorithms: SC($\max$, $\ell$, $\hat{I}”$, T) computes a single $\hat{I}”$-cluster where $P$ has at least $\ell$ vertices and maximises the cardinality $m$ of $\mathcal{P}$. SC($m$, $\max$, $\hat{I}”$, T) computes a single $\hat{I}”$-cluster where $\mathcal{P}$ has cardinality $m$ and maximises the complexity $\ell$ of $P$. We use such maximum-cardinality clusters in a greedy clustering algorithm. We provide an efficient implementation of SC($\max$, $\ell$, $\hat{I}”$, T) and SC($m$, $\max$, $\hat{I}”$, 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 $\hat{I}”$ and T, these two functions always output a point on the Pareto front of some bivariate function $\hat{I}¸(\ell ,m)$. We design a new algorithm PSC($\hat{I}”$, T) that in $O(n^2{\log }^{4}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($\hat{I}”$, T) as a subroutine improves the clustering quality and performance even further.

To appear at SoCG 2025