Faster, Deterministic and Space Efficient Subtrajectory Clustering

Abstract

Given a trajectory T and a distance ∆, we wish to find a set C of curves of complexity at most ℓ, such that we can cover T with subcurves that each are within Fréchet distance ∆ to at least one curve in C. We call C an (ℓ, ∆)-clustering and aim to find an (ℓ, ∆)-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 (ℓ, Θ(∆))-clustering of roughly optimal size. We present algorithms that construct (ℓ, 4∆)-clusterings of O(k log n) size, where k is the size of the optimal (ℓ, ∆)-clustering. We use O(n3) space and O(kn3 log4 n) time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in ∆) and size (whenever ℓ ∈ Ω(log n/ log k)). We offer deterministic running times improving known expected bounds by a factor near-linear in ℓ. Additionally, we match the space usage of prior work, and improve it substantially, by a factor super-linear in nℓ, when compared to deterministic results.