李想+章登义

摘 要：针对从移动端采集到的移动对象原始轨迹序列的化简，定义了一种回溯化简框架，通过线性预测来控制化简的时机，对当前时刻到回溯的历史轨迹的起始时刻之间的原始轨迹进行离线化简，化简采用时态距离作为误差度量方法.在回溯化简框架下，首先利用每次离线化简后新产生的化简点构建多个向量，通过向量计算出预测速度方向，旨在缩小预测方向与未来真实速度方向的差异；然后利用点集合存储有向无环图中必需访问边来降低最优线化简算法的时间复杂度.第1组实验表明，相对于直接使用最近两个位置点计算速度方向，抖动较为剧烈的原始轨迹在新的预测速度方向下的化简率更高，说明预测速度方向比切线速度方向更接近移动对象的未来运动方向；第2组实验表明，优化后离线化简算法的时间性能有所提高，说明减少边的访问量确实能够降低算法的时间开销.

关键词：移动对象数据库；轨迹；化简；回溯；线性预测；时态距离

中图分类号：TP301 文献标志码：A

Backtracking Based Method for On-line

Trajectory Simplification of Moving Objects

LI Xiang， ZHANG Dengyi

（School of Computer， Wuhan University， Wuhan 430072， China）

Abstract：For the simplification for the original trajectory sequence of the moving object collected from the mobile devices， this paper defined a kind of backtracking based simplification framework， which used the linear prediction and length of simplification queue to dominate the time of simplification， and simplified the original trajectory sequence between the present moment and starting time of a retrospective historical trajectory adopting the method of temporal distance as the error metric. In the backtracking based simplification framework， this paper first utilized the new reduced points to construct several vectors and predicted the velocity， which could narrow the gap between the prediction and actual velocity in the future. This paper then utilized the point sets to store the edges in the directed acyclic graph needed in the access to reduce time complexity of the algorithm. The first experiment shows that the reduction rate using the optimal velocity prediction is greater than that of the original velocity prediction with the high fluctuant trajectory data. It suggests that the predicted velocity is closer to the actual velocity in the future moving direction than that in the tangent direction. The second experiment shows that the time performances of the optimized simplification algorithm are improved. This study shows that the reduction of the visits of the edges can decrease the time overhead of the algorithm.

Key words：moving object database； trajectories； simplification； backtracking； linear prediction； temporal distance

如今GPS设备的普及使得基于位置的服务（Location Based Services，LBS）市场迅速增长，催生了大量的基于位置的应用.例如在车辆导航系统中，新的路线规划服务需要根据环境、车辆运行状态和道路交通规则[1]，综合考虑多个行车成本（时间、距离、油耗等），通过收集和分析车辆的历史轨迹得到驾驶员的行车偏好，然后为其定制个性化的行车路線[2]. 而“未来1小时路况预……