TY - JOUR

T1 - Finding long and similar parts of trajectories

AU - Buchin, K.

AU - Buchin, M.

AU - Kreveld, van, M.J.

AU - Luo, J.

PY - 2011

Y1 - 2011

N2 - A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give (1+e)-approximation algorithms, for both fixed duration and when only a minimum duration is specified.
Keywords: Trajectory analysis; Similarity measure; Moving objects

AB - A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give (1+e)-approximation algorithms, for both fixed duration and when only a minimum duration is specified.
Keywords: Trajectory analysis; Similarity measure; Moving objects

U2 - 10.1016/j.comgeo.2011.05.004

DO - 10.1016/j.comgeo.2011.05.004

M3 - Article

VL - 44

SP - 465

EP - 476

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 9

ER -