Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (8): 254-259.DOI: 10.3778/j.issn.1002-8331.1510-0297

Previous Articles     Next Articles

Online GPS trajectory data compression based on offset calculation

FAN Qingfu, ZHANG Lei, LIU Leijun, BAO Suning, FANG Chen   

  1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China
  • Online:2017-04-15 Published:2017-04-28


樊庆富,张  磊,刘磊军,鲍苏宁,房  晨   

  1. 中国矿业大学 计算机科学与技术学院,江苏 徐州 221116

Abstract: In view of the fact that the existing online Global Positioning System(GPS) trajectory data compression algorithm based on the offset calculation cannot effectively be applied to the key point insufficient evaluation, this paper proposes a new online trajectory data compression algorithm based on the offset calculation named Key-Predecessor Fix Algorithm(KPFA). This algorithm calculates the Synchronization Euclidean Distance(SED)and the accumulated offset to find out the key points with large amount of information. At the same time, it sets the threshold to correct the trajectory points between the current key point and the last key point to keep the trajectory information more completely. The experimental results show that compared with the Opening Window Time Ratio(OPW-TR)and Spatial Quality Simplification Heuristic Efficient(SQUISH-E) algorithms the average SED error of KPFA is the smallest and the running time is the fastest maintenance in 100, 000 ms when the compression ratio is the same. The KPFA has higher accuracy on the amount of information of the trajectory point evaluation and the running time is more stable.

Key words: online trajectory compression, synchronous Euclidean distance, offset calculation, evaluation error

摘要: 针对现有基于偏移量计算的在线GPS轨迹数据压缩算法不能有效评估关键点的问题,提出基于偏移量计算的在线GPS轨迹数据压缩算法——关键点前继修正算法(KPFA)。该算法通过计算同步欧式距离(SED)累积偏移量来发现轨迹点中信息量较大的关键点,同时设置阈值对关键点之前和上一个关键点之后的轨迹点进行修正,更好地保留轨迹信息。实验结果表明,和按时间比例的开窗算法(OPW-TR)及启发式空间质量简化算法的改进算法(SQUISH-E)相比,压缩率相同时KPFA的平均SED误差最小,并且运行时间最快且维持在100 000 ms。KPFA算法对轨迹点的信息量评估准确度更高,运行时间更稳定。

关键词: 在线轨迹压缩, 同步欧式距离, 偏移量计算, 评估误差