Simplification of Trajectory Streams

Cheng, Siu-Wing

doi:10.1007/s00454-026-00838-6

Simplification of Trajectory Streams

2026-03-01

0

PRE

AI

DOI：10.1007/s00454-026-00838-6

Original

Original request for help

Save

Abstract

En 中文

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 & eacute;chet distance dF in R-d for some constant d >= 2. Consider a polygonal curve r in R-d in a stream. We present a streaming algorithm that, for any e is an element of (0, 1) and delta > 0, maintains a curve a such that dF(a, r[v(1), v(i)]) <= (1 + e)delta and |a| <= 2 opt-2, where r[v(1), v(i)] is the prefix in the stream so far, and opt = min{|a|: dF(a, r[v(1), v(i)]) <= delta}. The working storage is O(epsilon(-alpha)), where alpha = 2(d-1)d/22 + d. Each vertex is processed in O(epsilon-(alpha) log 1e) time for d is an element of{2, 3} and O(epsilon(-alpha)) time for d >= 4. Thus, the whole curve r can be simplified in O(epsilon(-alpha) |r |log 1/epsilon ) time. Ignoring polynomial factors in 1/e, this running time is a factor |r| faster than the best static algorithm that offers the same guarantees. We present another streaming algorithm that, for any integer k >= 2 and any e is an element of (0, 10 /17 ), maintains a curve a such that |a| <= 2k-2 and dF(a, r[v(1), v(i)]) <= (1 + e) & centerdot; min{dF(a, r[v(1), v(i)]) :|a|<= k}, where r[v(1), v(i)] is the prefix in the stream so far. The working storage is O((k epsilon-alpha +epsilon-(alpha +1)) log epsilon 1). Each vertex is processed in O(k epsilon(-(alpha +1)) log(2) 1/epsilon) time ford is an element of{2, 3} and O(k(epsilon-(alpha +1)) log 1/epsilon) time for d >= 4.

Keywords:

Streaming algorithm

Curve simplification

Fr & eacute

chet distance

Simplification of Trajectory Streams

Abstract

Journal

Organization