Faster, Deterministic and Space Efficient Subtrajectory Clustering

Abstract

Given a trajectory $T$ and a distance $\hat{I}”$, we wish to find a set $C$ of curves of complexity at most $\ell$, such that we can cover $T$ with subcurves that each are within Fréchet distance $\hat{I}”$ to at least one curve in $C$. We call $C$ an $(\ell ,\hat{I}”)$-clustering and aim to find an $(\ell ,\hat{I}”)$-clustering of minimum cardinality. This problem variant was introduced by Akitaya $et$ $al.$ (2021) and shown to be NP-complete. The main focus has therefore been on bicriteria approximation algorithms, allowing for the clustering to be an $(\ell ,\hat{I}˜(\hat{I}”))$-clustering of roughly optimal size. We present algorithms that construct $(\ell ,4\hat{I}”)$-clusterings of $\mathcal{O}(k\log n)$ size, where $k$ is the size of the optimal $(\ell ,\hat{I}”)$-clustering. We use $\mathcal{O}(n^3)$ space and $\mathcal{O}(k{n}^3{\log }^{4}n)$ time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in $\hat{I}”$) and size (whenever $\ell \in \hat{I}\text{c◯}(\log n/\log k)$). We offer deterministic running times improving known expected bounds by a factor near-linear in $\ell$. Additionally, we match the space usage of prior work, and improve it substantially, by a factor super-linear in $n\ell$, when compared to deterministic results.

25 pages, 9 figures