Simplification of Trajectory Streams
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908474490748928 |
|---|---|
| author | Cheng, Siu-Wing Huang, Haoqiang Jiang, Le |
| author_facet | Cheng, Siu-Wing Huang, Haoqiang Jiang, Le |
| contents | While there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present streaming algorithms for two such problems under the Fréchet distance $d_F$ in $\mathbb{R}^d$ for some constant $d \geq 2$.
Consider a polygonal curve $τ$ in $\mathbb{R}^d$ in a stream. We present a streaming algorithm that, for any $\varepsilon\in (0,1)$ and $δ> 0$, produces a curve $σ$ such that $d_F(σ,τ[v_1,v_i])\le (1+\varepsilon)δ$ and $|σ|\le 2\,\mathrm{opt}-2$, where $τ[v_1,v_i]$ is the prefix in the stream so far, and $\mathrm{opt} = \min\{|σ'|: d_F(σ',τ[v_1,v_i])\le δ\}$. Let $α= 2(d-1){\lfloor d/2 \rfloor}^2 + d$. The working storage is $O(\varepsilon^{-α})$. Each vertex is processed in $O(\varepsilon^{-α}\log\frac{1}{\varepsilon})$ time for $d \in \{2,3\}$ and $O(\varepsilon^{-α})$ time for $d \geq 4$ . Thus, the whole $τ$ can be simplified in $O(\varepsilon^{-α}|τ|\log\frac{1}{\varepsilon})$ time. Ignoring polynomial factors in $1/\varepsilon$, this running time is a factor $|τ|$ faster than the best static algorithm that offers the same guarantees.
We present another streaming algorithm that, for any integer $k \geq 2$ and any $\varepsilon \in (0,\frac{1}{17})$, maintains a curve $σ$ such that $|σ| \leq 2k-2$ and $d_F(σ,τ[v_1,v_i])\le (1+\varepsilon) \cdot \min\{d_F(σ',τ[v_1,v_i]): |σ'| \leq k\}$, where $τ[v_1,v_i]$ is the prefix in the stream so far. The working storage is $O((k\varepsilon^{-1}+\varepsilon^{-(α+1)})\log \frac{1}{\varepsilon})$. Each vertex is processed in $O(k\varepsilon^{-(α+1)}\log^2\frac{1}{\varepsilon})$ time for $d \in \{2,3\}$ and $O(k\varepsilon^{-(α+1)}\log\frac{1}{\varepsilon})$ time for $d \geq 4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23025 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simplification of Trajectory Streams Cheng, Siu-Wing Huang, Haoqiang Jiang, Le Computational Geometry While there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present streaming algorithms for two such problems under the Fréchet distance $d_F$ in $\mathbb{R}^d$ for some constant $d \geq 2$. Consider a polygonal curve $τ$ in $\mathbb{R}^d$ in a stream. We present a streaming algorithm that, for any $\varepsilon\in (0,1)$ and $δ> 0$, produces a curve $σ$ such that $d_F(σ,τ[v_1,v_i])\le (1+\varepsilon)δ$ and $|σ|\le 2\,\mathrm{opt}-2$, where $τ[v_1,v_i]$ is the prefix in the stream so far, and $\mathrm{opt} = \min\{|σ'|: d_F(σ',τ[v_1,v_i])\le δ\}$. Let $α= 2(d-1){\lfloor d/2 \rfloor}^2 + d$. The working storage is $O(\varepsilon^{-α})$. Each vertex is processed in $O(\varepsilon^{-α}\log\frac{1}{\varepsilon})$ time for $d \in \{2,3\}$ and $O(\varepsilon^{-α})$ time for $d \geq 4$ . Thus, the whole $τ$ can be simplified in $O(\varepsilon^{-α}|τ|\log\frac{1}{\varepsilon})$ time. Ignoring polynomial factors in $1/\varepsilon$, this running time is a factor $|τ|$ faster than the best static algorithm that offers the same guarantees. We present another streaming algorithm that, for any integer $k \geq 2$ and any $\varepsilon \in (0,\frac{1}{17})$, maintains a curve $σ$ such that $|σ| \leq 2k-2$ and $d_F(σ,τ[v_1,v_i])\le (1+\varepsilon) \cdot \min\{d_F(σ',τ[v_1,v_i]): |σ'| \leq k\}$, where $τ[v_1,v_i]$ is the prefix in the stream so far. The working storage is $O((k\varepsilon^{-1}+\varepsilon^{-(α+1)})\log \frac{1}{\varepsilon})$. Each vertex is processed in $O(k\varepsilon^{-(α+1)}\log^2\frac{1}{\varepsilon})$ time for $d \in \{2,3\}$ and $O(k\varepsilon^{-(α+1)}\log\frac{1}{\varepsilon})$ time for $d \geq 4$. |
| title | Simplification of Trajectory Streams |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2503.23025 |