Simplification of Trajectory Streams

Let $n=|\tau |$. In $ℝ$, if the vertices of $\sigma$ are restricted to lie on $\tau$ (anywhere), then $|\sigma |$ can be minimized in $O(n)$ time [24]; if the vertices of $\sigma$ must be a subset of those of $\tau$, it takes $O(n)$ time to compute $\sigma$ such that $|\sigma |$ is at most two more than the minimum [10]. In $ℝ$, there is a data structure [25] that, for any given $\delta$, reports a curve $\sigma$ with the minimum $|\sigma |$ such that the vertices of $\sigma$ lie on $\tau$ (anywhere) and $d_F(\sigma ,\tau )\le \delta$. The query time is $O(|\sigma |)$, and the preprocessing time is $O(n)$.

In ${ℝ}^2$, a curve $\sigma$ with minimum $|\sigma |$ such that $d_F(\sigma ,\tau )\le \delta$ can be computed in $O(n^2{\log }^{2}n)$ time [15]. In ${ℝ}^d$ for $d\ge 3$, if the vertices of $\sigma$ must be a subset of those of $\tau$, then $|\sigma |$ can be minimized in $O(n^3)$ time [5, 24, 26]. If there is no restriction on the vertices of $\sigma$, it has been recently shown that $|\sigma |$ can be minimized in $O\left({(|\sigma |n)}^{O(d|\sigma |)}\right)$ time [9].

Faster algorithms have been developed by allowing inexact output. Let $\kappa (\tau ,r)$ be the minimum simplified curve size for an error $r$. In ${ℝ}^2$, it was shown [3] that for any $\delta >0$, a curve $\sigma$ can computed in $O(n\log n)$ time such that $d_F(\sigma ,\tau )\le \delta$ and $|\sigma |\le \kappa (\tau ,\delta /2)$. It is possible that $\kappa (\tau ,\delta /2)\gg \kappa (\tau ,\delta )$. A better control of the curve size has been obtained later. In ${ℝ}^d$, it was shown [24] that for any $\epsilon \in (0,1)$ and $\delta >0$, a curve $\sigma$ can be constructed in $O({\epsilon }^{2-2d}{n}^2\log n\log \log n)$ time such that $d_F(\sigma ,\tau )\le (1+\epsilon )\delta$ and $|\sigma |\le 2\kappa (\tau ,\delta )-2$.¹¹1In [24], the first and last vertices of $\sigma$ are restricted to be the same as those of $\tau$. Later, it was shown [8] that for any $\alpha ,\epsilon \in (0,1)$ and $\delta >0$, a curve $\sigma$ can be computed in $\tilde{O}\left(n^{O(1/\alpha )}\cdot {(d/(\alpha \epsilon ))}^{O(d/\alpha )}\right)$ time such that $d_F(\sigma ,\tau )\le (1+\epsilon )\delta$ and $|\sigma |\le (1+\alpha )\cdot \kappa (\tau ,\delta )$.

The algorithms above for $d\ge 2$ do not fit the streaming setting [3, 5, 8, 9, 15, 24, 26]. In [3], the simplified curve $\sigma$ is a subsequence of the vertices in $\tau$, and the vertices of $\sigma$ are picked from $\tau$ in a traversal of $\tau$. Given the last pick $v_i$, for any $j>i$, whether $v_j$ should be included in $\sigma$ is determined by examining the subcurve $\tau [v_i,v_j]$. This requires an $O(n)$ working storage which is too large. If the algorithms in [5, 8, 9, 15, 24, 26] are used in the streaming setting, the processing time per vertex would be $O(n)$ or more which is too high.

In $ℝ$, for any given $k$, the data structure for $\delta$-simplification in [25] can be queried in $O(k)$ time to report a curve $\sigma$ such that $|\sigma |=k$, the vertices of $\sigma$ lie on $\tau$ (anywhere), and $d_F(\sigma ,\tau )$ is minimized. In ${ℝ}^d$, if the vertices of $\sigma$ must be a subset of those of $\tau$, it was shown [14] that a solution $\sigma$ can be computed in $O(n^4\log n)$ time such that $d_F(\sigma ,\tau )\le 7\cdot \min \left\{d_F({\sigma }^{\prime },\tau ):|{\sigma }^{\prime }|\le k,\text{no restriction on the vertices of }{\sigma }^{\prime }\right\}$. The factor 7 can be reduced to 4 by a better analysis [3]. Nevertheless, if this algorithm is used in the streaming setting, the vertex processing time would be $O(n^3\log n)$ or more, which is way too high.

A line simplification $\sigma$ of a stream $\tau$ is a subsequence of the vertices such that the first and last vertices of $\sigma$ are the first and last vertices in the stream so far. In ${ℝ}^2$, for any integer $k\ge 2$ and any $\epsilon \in (0,1)$, it was shown [1, 2] how to maintain $\sigma$ such that $|\sigma |\le 2k$ and $d_F(\sigma ,\tau )\le (4\sqrt{2}+\epsilon )\cdot {\mathrm{opt}}_k$, where ${\mathrm{opt}}_k=\min \{d_F({\sigma }^{\prime },\tau ):\text{line simplification }{\sigma }^{\prime }\text{ of }\tau ,|{\sigma }^{\prime }|\le k\}$. The working storage is $O(k^2+k{\epsilon }^{-1/2})$. Each vertex is processed in $O(k\log \frac{1}{\epsilon })$ amortized time. There are also streaming software systems for this problem that minimize some local error measures (e.g. [13, 20, 21, 23]); however, they do not provide any guarantee on the global similarity between $\tau$ and the output curve.

The discrete Fréchet distance $d_{\text{dF}}(\sigma ,\tau )$ is obtained with the restriction that the parameterizations ${\rho }_{\sigma }$ and ${\rho }_{\tau }$ must match the vertices of $\sigma$ to those of $\tau$ and vice versa. Note that $d_{\text{dF}}(\sigma ,\tau )\ge d_F(\sigma ,\tau )$ and $d_{\text{dF}}(\sigma ,\tau )\gg d_F(\sigma ,\tau )$ in the worst case.

There are several results in ${ℝ}^3$ [4]. A curve $\sigma$ with the minimum $|\sigma |$ such that $d_{\text{dF}}(\sigma ,\tau )\le \delta$ can be computed in $O(n\log n)$ time; if the vertices of $\sigma$ must be a subset of those of $\tau$, the computation time increases to $O(n^2)$. On the other hand, if $k$ is given instead of $\delta$, a curve $\sigma$ such that $|\sigma |=k$ and $d_{\text{dF}}(\sigma ,\tau )$ is minimized can be computed in $O(kn\log n\log (n/k))$ time; if the vertices of $\sigma$ must a subset of those of $\tau$, the computation time increases to $O(n^3)$.

In ${ℝ}^d$, a streaming $k$-simplification algorithm was proposed in [11] with guarantees on $d_{\text{dF}}(\sigma ,\tau )$, where $\tau$ is the curve seen in the stream so far. It was shown that for any integer $k\ge 2$ and any $\epsilon \in (0,1)$, a curve $\sigma$ can be computed such that $|\sigma |\le k$ and $d_{\text{dF}}(\sigma ,\tau )\le 8\cdot \min \{d_{\text{dF}}({\sigma }^{\prime },\tau ):|{\sigma }^{\prime }|\le k\}$. The working storage is $O(kd)$.

Improved results have been obtained subsequently [12]. For the streaming $\delta$-simplification problem, there is a streaming algorithm in ${ℝ}^d$ that, for any $\gamma >1$, computes a curve $\sigma$ such that $d_{\text{dF}}(\sigma ,\tau )\le \delta$ and $|\sigma |\le \kappa (\tau ,\delta /\gamma )$. This algorithm relies on a streaming algorithm for maintaining a $\gamma$-approximate minimum closing ball (MEB) of points in ${ℝ}^d$; the processing time per vertex is asymptotically the same as the $\gamma$-approximate MEB streaming algorithm. There are two streaming $k$-simplification algorithms in [12]. The first one uses $O(\frac{1}{\epsilon }kd\log \frac{1}{\epsilon })+O{(\epsilon )}^{-(d+1)/2}{\log }^2\frac{1}{\epsilon }$ working storage and maintains a curve $\sigma$ such that $|\sigma |\le k$ and $d_{\text{dF}}(\sigma ,\tau )\le (1+\epsilon )\cdot \min \{d_{\text{dF}}({\sigma }^{\prime },\tau ):|{\sigma }^{\prime }|\le k\}$. The second algorithm uses $O(\frac{1}{\epsilon }kd\log \frac{1}{\epsilon })$ working storage and maintains a curve $\sigma$ such that $|\sigma |\le k$ and $d_{\text{dF}}(\sigma ,\tau )\le (1.22+\epsilon )\cdot \min \{d_{\text{dF}}({\sigma }^{\prime },\tau ):|{\sigma }^{\prime }|\le k\}$.

Our algorithm outputs vertices occasionally and maintains some vertices in the working storage. The simplified curve $\sigma$ for the prefix $\tau [v_1,v_i]$ in the stream so far consists of vertices that have been output and vertices in the working storage. Vertices that have been output cannot be modified, so they form a prefix of all simplified curves to be produced in the future for the rest of the stream.

For any $\epsilon \in (0,1)$ and any $\delta >0$, our algorithm produces a curve $\sigma$ for the prefix $\tau [v_1,v_i]$ in the stream so far such that $d_F(\sigma ,\tau [v_1,v_i])\le (1+\epsilon )\delta$ and $|\sigma |\le 2\kappa (\tau [v_1,v_i],\delta )-2$. Let $\alpha =2(d-1){\lfloor d/2\rfloor }^2+d$. The working storage is $O({\epsilon }^{-\alpha })$. Each vertex in the stream is processed in $O({\epsilon }^{-\alpha }\log \frac{1}{\epsilon })$ time for $d\in \{2,3\}$ and $O({\epsilon }^{-\alpha })$ time for $d\ge 4$. If our algorithm is used in the static case, the running time on a curve of size $n$ is $O({\epsilon }^{-\alpha }n\log \frac{1}{\epsilon })$. Ignoring polynomial factors in $1/\epsilon$, our time bound is a factor $n$ smaller than the $O({\epsilon }^{2-2d}{n}^2\log n\log \log n)$ running time of the best static algorithm that achieves the same error and size bounds [24].

Intuitively, our streaming algorithm finds a line segment that stabs as many balls as possible that are centered at consecutive vertices of $\tau$ with radii $(1+O(\epsilon ))\delta$. If such a line segment ceases to exist upon the arrival of a new vertex, we start a new line segment. Concatenating these segments forms the simplified curve. For efficiency, we approximate each ball by covering it with grid cells of $O(\epsilon \delta )$ width. In [24], vertex balls and their covers by grid cells of $O(\epsilon \delta )$ width are also used. Connections between all pairs of balls are computed to create a graph such that the simplified curve corresponds to a shortest path in the graph. In contrast, we maintain some geometric structures so that we can read off the next line segment from them. We prove an $O({\epsilon }^{-\alpha })$ bound on the total size of these structures, which yields the desired working storage and processing time per vertex.

A memory budget may cap the size of the simplified curve, motivating the streaming $k$-simplification problem. For example, in some wildlife tracking applications, the location-acquisition device is not readily accessible after deployment, and data is only offloaded from it after an extended period [19].

Our algorithm maintains the simplified curve $\sigma$ in the working storage for the prefix $\tau [v_1,v_i]$ in the stream so far. For any $k\ge 2$ and any $\epsilon \in (0,\frac{1}{17})$, our algorithm guarantees that $|\sigma |\le 2k-2$ and $d_F(\sigma ,\tau [v_1,v_i])\le (1+\epsilon )\cdot \min \{d_F({\sigma }^{\prime },\tau [v_1,v_i]):|{\sigma }^{\prime }|\le k\}$. Recall that $\alpha =2(d-1){\lfloor d/2\rfloor }^2+d$. The working storage is $O((k{\epsilon }^{-1}+{\epsilon }^{-(\alpha +1)})\log \frac{1}{\epsilon })$. Each vertex in the stream is processed in $O(k{\epsilon }^{-(\alpha +1)}{\log }^2\frac{1}{\epsilon })$ time for $d\in \{2,3\}$ and $O(k{\epsilon }^{-(\alpha +1)}\log \frac{1}{\epsilon })$ time for $d\ge 4$. We first simplify as in the case of $\delta$-simplification. When the simplified curve reaches a size of $2k-1$, the key idea is to run our $\delta$-simplification algorithm with a suitable error tolerance to bring its size down to $2k-2$.

There is only one prior streaming $k$-simplification algorithm [1, 2]. It works in ${ℝ}^2$. It restricts the vertices of the simplified curve $\sigma$ to be a subset of those of $\tau$, whereas our algorithm does not. It uses $O(k^2+k{\epsilon }^{-1/2})$ working storage, processes each vertex in $O(k\log \frac{1}{\epsilon })$ amortized time, and guarantees that $|\sigma |\le 2k$ and $d_F(\sigma ,\tau )\le (4\sqrt{2}+\epsilon )\cdot \mathrm{optimum}$ under the requirement that the vertices of $\sigma$ must be a subset of those of $\tau$. For $d=2$, our algorithm uses $O((k{\epsilon }^{-1}+{\epsilon }^{-5})\log \frac{1}{\epsilon })$ working storage, processes each vertex in $O(k{\epsilon }^{-5}{\log }^2\frac{1}{\epsilon })$ worst-case time, and guarantees that $|\sigma |\le 2k-2$ and $d_F(\sigma ,\tau )\le (1+\epsilon )\cdot \mathrm{optimum}$. Ignoring the restriction on the vertices of $\sigma$, we offer a better approximation ratio for $d_F(\sigma ,\tau )$. Although our vertex processing time bound is larger, it is worst-case instead of amortized. The comparison between working storage depends on the relative magnitudes of $k$ and $1/\epsilon$.

The guarantees on $\sigma$ follow from Lemma 2. We will bound the number of support hyperplanes and complexities of $S_j[p]$ and $F(S_{j-1}[p],p)$. The working storage and processing time then follow from Lemma 1(ii) and the fact that $|P|=O({\epsilon }^{-d})$.

A bounding halfspace of a convex polytope $O$ is a halfspace that contains $O$ and is bounded by the support hyperplane of a facet of $O$. We count the bounding halfspaces of $S_j[p]$. Some are bounding halfspaces of $F(S_{j-1}[p],p)$ whose boundaries pass through $p$ and are tangent to $S_{j-1}[p]$. We call them the pivot bounding halfspaces. The remaining ones are bounding halfspaces of $\mathrm{conv}(G_{v_a})$ for some $a\le j$. We call these non-pivot bounding halfspaces.

Since $\mathrm{conv}(G_{v_a})$’s are translates of each other, their facets share a set $V$ of unit outward normals. We have $|V|\le |\mathrm{conv}(G_{v_a})|=O({\epsilon }^{(1-d)\lfloor d/2\rfloor })$. No two facets of $S_j[p]$ have the same vector in $V$ because the two corresponding bounding halfspaces would be identical or nested – neither is possible. This feature helps us to prevent a cascading growth in the complexities of $S_j[p]$ in the inductive construction.

Take a pivot bounding halfspace $h$ of $S_j[p]$. Suppose that $h$ was introduced for the first time as a bounding halfspace of $S_i[p]$ for some $i\le j$. The boundary of $h$, denoted by $\partial h$, passes through $p$ and is tangent to $S_{i-1}[p]$ at a $(d-2)$-dimensional face $f$ of $S_{i-1}[p]$. Let $g_1$ and $g_2$ be the bounding halfspaces of $S_{i-1}[p]$ whose boundaries contain the two facets of $S_{i-1}[p]$ incident to $f$. We make three observations. First, $F(S_{i-1}[p],p)$ lies inside the cone $C_i$ of rays that shoot from $p$ towards $S_{i-1}[p]$. Second, $h$ is a bounding halfspace of $C_i$. Third, $S_a[p]\subseteq C_i$ for all $a\in [i,j]$.

We claim that neither $\partial g_1$ nor $\partial g_2$ passes through $p$. Neither $g_1$ nor $g_2$ is equal to $h$ because $h$ was not introduced before $S_i[p]$. If both $\partial g_1$ and $\partial g_2$ pass through $p$, then $f$ spans a $(d-2)$-dimensional affine subspace $\mathrm{\ell }$ that passes through $p$. But then $\partial h$ meets $C_i$ at $\mathrm{\ell }$ only, which is a contradiction because $\partial h$ should support a facet of $S_j[p]$. If either $\partial g_1$ or $\partial g_2$ passes through $p$, say $\partial g_2$, then the affine subspace spanned by $f$ does not pass through $p$. But then $p$ and $f$ span a unique hyperplane, giving the contradiction that $g_2=h$.

By our claim, $g_1$ and $g_2$ are non-pivot bounding halfspaces of $S_{i-1}[p]$. We charge $h$ to $({\varphi }_1,{\varphi }_2)$ or $({\varphi }_2,{\varphi }_1)$, where ${\varphi }_1$ and ${\varphi }_2$ are the outward unit normals of $g_1$ and $g_2$, respectively. The pair $({\varphi }_1,{\varphi }_2)$ is charged if a ray that shoots from $p$ to an interior point of $g_1\cap g_2$ arbitrarily near $\partial g_1\cap \partial g_2$ hits $\partial g_1$ before $\partial g_2$. Otherwise, the pair $({\varphi }_2,{\varphi }_1)$ is charged. Suppose that $h$ is charged to $({\varphi }_1,{\varphi }_2)$. We argue that $({\varphi }_1,{\varphi }_2)$ is not charged again at some $(d-2)$-dimensional face of $S_a[p]$ for all $a\in [i,j-1]$ due to another pivot bounding halfspace of $S_j[p]$.

Assume to the contrary that $({\varphi }_1,{\varphi }_2)$ is charged again at some $(d-2)$-dimensional face of $S_b[p]$ for some $b\in [i,j-1]$ due to a pivot bounding halfspace $h^{\prime }$ of $S_j[p]$. Either the dimension of $\partial h^{\prime }\cap C_i$ is zero or one, or the dimension of $\partial h^{\prime }\cap C_i$ is two. In the first case, $\partial h^{\prime }$ cannot support any facet of $S_j[p]$, a contradiction. In the second case, since $h^{\prime }$ is charged to the same ordered pair $({\varphi }_1,{\varphi }_2)$, $\partial h^{\prime }$ must separate $S_b[p]$ from $\partial h$. Therefore, the cone of rays $C_b$ that shoot from $p$ towards $S_b[p]$ meets $\partial h$ only at $p$. However, $S_j[p]\subseteq C_b$, which means that $\partial h$ cannot support any facet of $S_j[p]$, a contradiction.

In all, $S_j[p]$ has $O({\epsilon }^{(1-d)\lfloor d/2\rfloor })$ non-pivot bounding halfspaces and at most $|V|(|V|-1)=O({\epsilon }^{2(1-d)\lfloor d/2\rfloor })$ pivot bounding halfspaces. The same bounds hold for $S_{j-1}[p]$. If a support hyperplane $L$ of $F(S_{j-1}[p],p)$ is not a support hyperplane of $S_{j-1}[p]$, then $L$ passes through $p$ and is tangent to $S_{j-1}[p]$ at some $(d-2)$-dimensional face $f$. Since $L$ is different from the support hyperplanes of the two facets of $S_{j-1}[p]$ incident to $f$, these two hyperplanes do not pass through $p$. So the two facets incident to $f$ induce some non-pivot bounding halfspaces of $S_{j-1}[p]$, implying that $F(S_{j-1}[p],p)$ has $O({\epsilon }^{2(1-d)\lfloor d/2\rfloor })$ bounding halfspaces. It follows that $\left|S_j[p]\right|$ and $\left|F(S_{j-1}[p],p)\right|$ are $O({\epsilon }^{2(1-d){\lfloor d/2\rfloor }^2})$. $◀$

Consider the run of Simplify$(\epsilon ,\widehat{\delta })$ on $\xi$. Let $p_{i_1},p_{i_2}\mathrm{\dots }$ be the vertices in order along $\xi$ at which Simplify starts a new segment. Note that $i_1=1$ and $i_{j+1}\ge i_j+2$ for all $j$.

Simplify replaces each subcurve $\xi [p_{i_j},p_{i_{j+1}-1}]$ by a segment. The simplified curve is a concatenation of these segments. Since $|\xi |=2k-1$, there must be an index $j$ such that $i_{j+1}>i_j+2$ so that Simplify$(\epsilon ,\widehat{\delta })$ simplifies $\xi$ to a curve of size at most $2k-2$. Let $b=\min \{j:i_{j+1}>i_j+2\}$. Because $i_1=1$ and $i_{j+1}=i_j+2$ for all $j\in [b-1]$, we know that $i_j$ is odd for every $j\in [b]$ and $i_b+1$ is even. It follows from the choice of $b$ that Simplify does not start a new segment at $p_{i_b+2}$. By the working of Simplify$(\epsilon ,\widehat{\delta })$, there is a grid point $p$ in $G_{p_{i_b}}$ (defined with $\delta =\widehat{\delta }$) such that $S_{i_b+2}[p]\ne \mathrm{\varnothing }$. By the reasoning in the proof of Lemma 2, for any point $x\in S_{i_b+2}[p]$, $d_F(px,\xi [p_{i_b},p_{i_b+2}])\le (1+\epsilon )\widehat{\delta }$. On the other hand, by Lemma 4, $d_F(px,\xi [p_{i_b},p_{i_b+2}])\ge \frac{1}{2}d(p_{i_b+1},p_{i_b}{p}_{i_b+2})$. Hence, $(1+\epsilon )\widehat{\delta }\ge \frac{1}{2}d(p_{i_b+1},p_{i_b}{p}_{i_b+2})\ge \frac{1}{2}\min \left\{d(p_j,p_{j-1}{p}_{j+1}):j\in [2,2k-2],j\text{ is even}\right\}$.