Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves
Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves
复制标题
DOI：
--
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Frederik Brüning;H. Akitaya;E. Chambers;Anne Driemel
中科院分区：
文献类型：
--
作者：
Frederik Brüning;H. Akitaya;E. Chambers;Anne Driemel
我们研究了Fr 'echet距离下的子轨迹聚类。给定一个或多个轨迹，任务是将轨迹分成几个部分，使得这些部分具有良好的聚类结构。我们通过一个新的集合覆盖公式来处理这个问题，我们认为它提供了一个自然的形式化的问题，因为它在许多应用程序中进行了研究。给定一条多边形曲线P，n个顶点的维数为固定，k为整数，$\ell \geq 1$，真实的值$\Delta>0$，目标是找到k条中心曲线，其复杂度至多为$\ell$，使得P上的每一点都被一条子轨迹所覆盖，该子轨迹与k条中心曲线之一（$\leq \Delta$）具有较小的Fr\'echet距离.在许多应用场景中，人们感兴趣的是寻找复杂度小的集群，这是由参数$\ell$控制的。我们的主要结果是一个双准则近似算法：如果存在一个解决方案，给定的参数$k$，$\ell$，$\Delta$，那么我们的算法找到一组$k '$中心曲线的复杂性最多$\ell$，覆盖半径$\Delta'$，$k' \在O（k\ell^2\log（k \ell））$，和$\Delta'\leq 19 \Delta$。此外，在这些近似范围内，我们可以最小化$k$，同时保持其他参数固定。如果$\ell$是一个与$n$无关的常数，那么，簇数$k$的近似因子是$O（\log k）$，半径$\Delta$的近似因子是常数。在这种情况下，算法的预期运行时间为$ \tilde{O}\left（k m^2 + mn\right）$，使用空间为$O（n+m）$，其中$m=\lceil\frac{L}{\Delta}\rceil$，$L$是曲线$P$的总弧长。
We study subtrajectory clustering under the Fr\'echet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal 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 curves of complexity at most $\ell$ such that every point on $P$ is covered by a subtrajectory that has small Fr\'echet distance to one of the $k$ center curves ($\leq \Delta$). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter $\ell$. Our main result is a bicriterial approximation algorithm: if there exists a solution for given parameters $k$, $\ell$, and $\Delta$, then our algorithm finds a set of $k'$ center curves of complexity at most $\ell$ with covering radius $\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$ while keeping 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$ is the total arclength of the curve $P$.