| Title: |
Faster, Deterministic and Space Efficient Subtrajectory Clustering |
| Authors: |
van der Hoog, Ivor; van der Horst, Thijs; Ophelders, Tim; Sub Geometric Computing; Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele |
| Publication Year: |
2025 |
| Subject Terms: |
clustering; Fréchet distance; set cover; Software |
| Description: |
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. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482988 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482988 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.6AE3D69D |
| Database: |
BASE |