Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better

Trajectory analysis is a broad field ranging from gait analysis of full-body motion trajectories [16, 20, 13], via traffic analysis [21] and epidemiological hotspot detection [25] to Lagrangian analysis of particle simulations [24]. Using the current availability of cheap tracking technology, vast amounts of unstructured spatio-temporal data are collected. Clustering is a fundamental problem in this area and can be formulated under various similarity metrics, among them the Fréchet distance. However, the unstructured nature of trajectory data poses the additional challenge that the data first needs to be segmented before the trajectory segments, which we call subtrajectories, can be clustered in a metric space. Subtrajectory clustering aims to find clusters of subtrajectories that represent complex patterns that reoccur along the trajectories [1, 8, 17], such as commuting patterns in traffic data.

We study two variants of a problem posed by Akitaya, Brüning, Chambers, and Driemel [3], which are based on the well-known set cover and coverage maximization problems. Both rely on the definition of a geometric set system built using metric balls under the Fréchet distance. Given a polygonal curve, we are asked to produce a set of “center” curves that either

1. 1.

   has minimum cardinality and covers the entirety of the input curve, or

2. 2.

   covers as much as possible of the input curve under cardinality constraints.

In either setting a point $p$ of the input-curve is considered as “covered”, if there is a subcurve ${\pi }_p$ of the input curve that contains $p$ and has small Fréchet distance to some center curve. Note that a point $p$ may be covered by multiple center curves. For the precise formulation refer to Section 2. This formulation extends immediately to a set of input curves – instead of one – where one is now tasked to cover the entirety (respectively as much as possible) of all points on all input curves combined.

In this paper we study the continuous variant of the problem where we need to cover the continuous set of points given by the input polygonal curve. It is instructive, however, to first consider a discrete variant of the set cover instance as follows. Given a discrete point sequence $A=a_1,\mathrm{\dots },a_n$, consider the set of contiguous subsequences of the form $A_{ij}=a_i,\mathrm{\dots },a_j$. We say $a_k$ is contained in the set defined by $A_{ij}$ if there exist $i^{\prime }\le k\le j^{\prime }$ such that $A_{i^{\prime }{j}^{\prime }}$ is similar to $A_{ij}$. Note that a full specification of this set system has size $\mathrm{\Theta }(n^3)$ in the worst case. This phenomenon is shared with the continuous setting where all known discretizations lead to a cubic-size set system. In this paper, we examine the question of whether we can obtain subcubic-time algorithms by internally representing the set system implicitly.

An edge is a map $e:[0,1]\to {ℝ}^d$ defined by two points $p,q\in {ℝ}^d$ as the linear interpolation $t\mapsto p+t(q-p)$. A polygonal curve is a map $P:[0,1]\to {ℝ}^d$ defined by an ordered set $(p_1,\mathrm{\dots },p_n)\subset {ℝ}^d$ as the result of concatenating the edges $(e_1,\mathrm{\dots },e_{n-1})$, where $e_i$ is the edge from $p_i$ to $p_{i+1}$. Any point $P(t)$ is said to lie on the edge $e_i$ if $t$ lies in the preimage of $e_i$. Any point $P(t)$ lies on at most two edges, exactly if it defines the endpoint of edge $e_i$ which coincides with the start point of $e_{i+1}$. The number of points $n$ defining the polygonal curve $P$ is its complexity, and we denote it by $|P|$. The set of all polygonal curves in ${ℝ}^d$ of complexity at most $\mathrm{\ell }$ we denote by ${𝕏}_{\mathrm{\ell }}^d$. For any polygonal curve $P$ and values $0\le s\le t\le 1$ we define $P[s,t]$ to be the subcurve of $P$ from $s$ to $t$, which itself is a polygonal curve of complexity at most $|P|$. For two polygonal curves $P$ and $Q$ we define the continuous Fréchet distance to be ${\mathrm{d}}_{ℱ}(P,Q)={inf}_{f,g}{\max }_{t\in [0,1]}\Vert P(f(t))-Q(g(t))\Vert$ where $f$ and $g$ range over all non-decreasing surjective functions from $[0,1]$ to $[0,1]$.

For a curve $Q\in {𝕏}_{\mathrm{\ell }}^d$ we denote the $\mathrm{\Delta }$-coverage ${\mathrm{Cov}}_P(\{Q\},\mathrm{\Delta })$ by ${\mathrm{Cov}}_P(Q,\mathrm{\Delta })$.

In this section we show that, given a curve $P$ of complexity $n$, there is a curve $S$ of complexity $n$ and a set ${𝒞}_S(P)$ of at most $𝒪(n^2\log n)$ subcurves of $S$, each of complexity at most $\mathrm{\ell }$, such that for any set of curves $C\subset {𝕏}_{\mathrm{\ell }}^d$ there is a subset $\widehat{C}\subset {𝒞}_S(P)$ of size $𝒪(|C|)$ such that ${\mathrm{Cov}}_P(C,\mathrm{\Delta })\subset {\mathrm{Cov}}_P(\widehat{C},4\mathrm{\Delta })$. This result is known and follows the line of research in [4, 9, 23]. All of these approaches compute a “maximally simplified” version $S$ of $P$, see also [10]. Our definition of a simplification follows the notion of pathlet-preserving simplifications from [23], as it yields the best constants.

By definition of the simplification $S$ of $P$ and the triangle inequality for any curve $\pi \in {𝕏}_{\mathrm{\ell }}^d$ there is a subcurve $\widehat{\pi }$ of $S$ of complexity at most $\mathrm{\ell }+2$ such that ${\mathrm{Cov}}_P(\pi ,\mathrm{\Delta })\subset {\mathrm{Cov}}_P(\widehat{\pi },4\mathrm{\Delta })$.

As was noted by Alt and Godau [2], the Fréchet distance of $S$ and $P$ is at most $\mathrm{\Delta }$ if and only if there is a monotone (in both $x$- and $y$-direction) path from $(0,0)$ to $(1,1)$ in $\mathrm{\Delta }$-free space of $S$ and $P$. They further observed that the free space inside any cell is described by an ellipse intersected with the cell and thus is convex and has constant complexity. Observe that two subcurves $P[a,c]$ and $S[b,d]$ have Fréchet distance at most $\mathrm{\Delta }$ if and only if there is a monotone (in both $x$- and $y$-direction) path from $(a,b)$ to $(c,d)$ in $\mathrm{\Delta }$-free space of $S$ and $P$.

Similar to [23], we define specific subcurves via the extremal points of the $4\mathrm{\Delta }$-free space.

The set containing all Type $(I)$-, $(II)$- and $(III)$-subcurves which we denote by ${𝒞}_S(P)$ describes the set of candidate curves similar to the candidate set from [23].

In this section we define an ordering of Type $(II)$ and Type $(III)$ subcurves in the set ${𝒞}_S(P)$ and introduce an approximate $\mathrm{\Delta }$-coverage called the proxy coverage. Later on, we show that a coarse representation of the proxy coverage can be maintained along the ordering.

Throughout this section we are given a polygonal curve $P$ of complexity $n$, values $\mathrm{\Delta }>0$ and $\mathrm{\ell }\le n$, as well as a simplification $S$ of $P$. As $|ℰ(e,P)|=𝒪(n)$ for any edge $e$, there are $𝒪(n\log \mathrm{\ell })$ Type $(I)$-, $𝒪(n^2)$ Type $(II)$- and $𝒪(n^2\log n)$ Type $(III)$-subcurves in ${𝒞}_S(P)$.

We are able to construct few sweep-sequences that already capture the entirety of ${𝒞}_S(P)$.

We focus our analysis on sweep-sequences of $ℰ(e,P)$ where for every tuple $({\epsilon }_a,{\epsilon }_b)$ it holds that $a\le b$ (refer to Figure 4). This analysis carries over to all sweep-sequences of $ℰ(e,P)$ by setting $e\leftarrow \mathrm{rev}(e)$, and thus to all sweep-sequences in ${𝔖}_e$.

We now turn to defining the proxy coverage on $P$ which approximates the $4\mathrm{\Delta }$-coverage.

We assume that for every edge $e$ and every the functions $l_i(\cdot )$ and $r_i(\cdot )$ of the free space ${𝒟}_{\mathrm{\Delta }}(e,P)$ can be evaluated in $𝒪(1)$ time.

The combinatorial representation can be partitioned into two sets, the global group $𝒢(e[s,t])$ consisting of all index-pairs $(i,j)\in ℛ(e[s,t])$ such that and the local group $ℒ(e[s,t])$ consisting of all index-pairs $(i,i)\in ℛ(e[s,t])$.

Let an edge $e$ of $S$ together with $0\le s\le t\le 1$ be given. We say an index $i$ is bad for $e[s,t]$, if all topmost points in cell $i$ of the free space of $e$ and $P$ are to the left of both $l_i(s)$ and $r_i(t)$, and both $l_i(s)$ and $r_i(t)$ are to the left of all bottom most points in cell $i$. Call this set of bad indices $ℬ(e[s,t])$. If $i\notin ℬ(e[s,t])$, $i$ is said to be good for $e[s,t]$. Intuitively, an index is bad if the free-space inside the cell is a diagonal from the top left to the bottom right. For Lemma 21 to hold, the definition a bad index is stronger and depends on $s$ and $t$.

We now turn to defining our central tool, the proxy coverage, which approximates the $\mathrm{\Delta }$-coverage and is easy to maintain. It is defined via a reduced combinatorial representation.

We observe that the proxy coverage can be expressed as a disjoint union via $\widetilde{𝒢}(e[s,t])$.

We extend the proxy coverage $\widehat{\mathrm{Cov}}$ to also be defined for Type $(I)$-subcurves of $S$, where we set ${\widehat{\mathrm{Cov}}}_P(S[s,t])={\mathrm{Cov}}_P(S[s,t],4\mathrm{\Delta })$. Overall, we see that for any $\pi \in {𝒞}_S(P)$ – not just Type $(II)$- and $(III)$-subcurves of $S$ – there are at most two elements ${\pi }_1,{\pi }_2\in {𝒞}_S(P)$ with

In this section we present an algorithm that given $𝔰\in {𝔖}_e$ maintains a symbolic representation of ${\widehat{\mathrm{Cov}}}_P(e[s,t])$ in (roughly) logarithmic time per element in $𝔰$. To this end we maintain the set $𝒰(e[s,t])$ of inclusion-wise maximal index-pairs $(i,j)$ such that there is a path from cell $i$ at height $s$ to cell $j$ at some height $\widehat{t}\le t$, which helps maintain $\widetilde{𝒢}(e[s,t])$ and $ℒ(e[s,t])\setminus ℬ(e[s,t])$. We want to highlight that maintaining $𝒢(e[s,t])$ and $ℒ(e[s,t])$ as a symbolic representation of the $4\mathrm{\Delta }$-Coverage can take total time in $\mathrm{\Theta }(n|{𝔖}_e|)$ (Figure 7) motivating our techniques.

Overall, we can maintain a symbolic representation of ${\widehat{\mathrm{Cov}}}_P(\cdot )$ during a sweep-sequence in total time $𝒪(n\log n)$ which enables the use of the maintained sets for batch point-queries.