Finding long and similar parts of trajectories
文献类型：会议论文
| 作者 | Kevin Buchin; Maike Buchin; Marc van Kreveld; Jun Luo |
| 出版日期 | 2009 |
| 会议名称 | 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009 |
| 英文摘要 | 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. When a minimum duration is specified for the subtrajectories, and they must start at exactly corresponding times in the inputtrajectories, we give a linear-time algorithm for computing the starting time and duration of the most similar subtrajectories. 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. When the two subtrajectories can start at different times in the two input trajectories, it appears difficult to give an exact algorithm for the most similar subtrajectories problem, even if the duration of the desired two subtrajectories is fixed to some length. We show that the problem can be solved approximately, and with a performance guarantee. More precisely, we present (1 + Ε)-approximation algorithms for computing the most similar subtrajectories of two input trajectories for the case where the duration is specified, and also for the case where only a minimum on the duration is specified. |
| 收录类别 | EI |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/2659]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2009 |
| 推荐引用方式 GB/T 7714 | Kevin Buchin,Maike Buchin,Marc van Kreveld,et al. Finding long and similar parts of trajectories[C]. 见:17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。