Faster, Deterministic and Space Efficient Subtrajectory Clustering
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915299107799040 |
|---|---|
| author | van der Hoog, Ivor van der Horst, Thijs Ophelders, Tim |
| author_facet | van der Hoog, Ivor van der Horst, Thijs Ophelders, Tim |
| contents | Given a trajectory $T$ and a distance $Δ$, 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 $Δ$ to at least one curve in $C$. We call $C$ an $(\ell,Δ)$-clustering and aim to find an $(\ell,Δ)$-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, Θ(Δ))$-clustering of roughly optimal size.
We present algorithms that construct $(\ell,4Δ)$-clusterings of $\mathcal{O}(k \log n)$ size, where $k$ is the size of the optimal $(\ell, Δ)$-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 $Δ$) and size (whenever $\ell \in Ω(\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13117 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster, Deterministic and Space Efficient Subtrajectory Clustering van der Hoog, Ivor van der Horst, Thijs Ophelders, Tim Computational Geometry F.2.2 Given a trajectory $T$ and a distance $Δ$, 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 $Δ$ to at least one curve in $C$. We call $C$ an $(\ell,Δ)$-clustering and aim to find an $(\ell,Δ)$-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, Θ(Δ))$-clustering of roughly optimal size. We present algorithms that construct $(\ell,4Δ)$-clusterings of $\mathcal{O}(k \log n)$ size, where $k$ is the size of the optimal $(\ell, Δ)$-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 $Δ$) and size (whenever $\ell \in Ω(\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. |
| title | Faster, Deterministic and Space Efficient Subtrajectory Clustering |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2402.13117 |