English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study subtrajectory clustering under the Fr\'echet distance. Given one ormore trajectories, the task is to split the trajectories into several parts,such that the parts have a good clustering structure. We approach this problemvia a new set cover formulation, which we think provides a naturalformalization of the problem as it is studied in many applications. Given apolygonal curve $P$ with $n$ vertices in fixed dimension, integers $k$, $\ell\geq 1$, and a real value $\Delta > 0$, the goal is to find $k$ center curvesof complexity at most $\ell$ such that every point on $P$ is covered by asubtrajectory that has small Fr\'echet distance to one of the $k$ center curves($\leq \Delta$). In many application scenarios, one is interested in findingclusters of small complexity, which is controlled by the parameter $\ell$. Ourmain result is a bicriterial approximation algorithm: if there exists asolution for given parameters $k$, $\ell$, and $\Delta$, then our algorithmfinds a set of $k'$ center curves of complexity at most $\ell$ with coveringradius $\Delta'$ with $k' \in O( k \ell^2 \log (k \ell))$, and $\Delta'\leq 19\Delta$. Moreover, within these approximation bounds, we can minimize $k$ whilekeeping the other parameters fixed. If $\ell$ is a constant independent of $n$,then, the approximation factor for the number of clusters $k$ is $O(\log k)$and the approximation factor for the radius $\Delta$ is constant. In this case,the algorithm has expected running time in $ \tilde{O}\left( k m^2 + mn\right)$and uses space in $O(n+m)$, where $m=\lceil\frac{L}{\Delta}\rceil$ and $L$ isthe total arclength of the curve $P$.

Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves