Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (1): 171-175.DOI: 10.11772/j.issn.1001-9081.2017061411

Previous Articles     Next Articles

Compression method for trajectory data based on prediction model

CHEN Yu, JIANG Wei, ZHOU Ji'en   

  1. Science and Technology Department, China UnionPay, Shanghai 201201, China
  • Received:2017-06-09 Revised:2017-09-13 Online:2018-01-10 Published:2018-01-22

基于预测模型的轨迹数据压缩方法

陈煜, 蒋伟, 周继恩   

  1. 中国银联股份有限公司 银联科技事业部, 上海 201201
  • 通讯作者: 蒋伟
  • 作者简介:陈煜(1972-),男,浙江乐清人,高级工程师,硕士,主要研究方向:大数据、人工智能;蒋伟(1990-),男,甘肃酒泉人,硕士,主要研究方向:数据管理、数据分析;周继恩(1976-),男,江苏吴江人,高级工程师,博士,主要研究方向:大数据、人工智能。

Abstract: A Compression method for Trajectory data based on Prediction Model (CTPM) was proposed to improve compression efficiency of massive trajectory data in road network environment. The temporal information and spatial information of the trajectory data were respectively compressed so that the compressed trajectory data was lossless in the spatial dimension and the error was bounded in the time dimension. In terms of space, the Prediction by Partial Matching (PPM) algorithm was used to predict the possible position of the next moment by the part trajectory that had been driven. And then the predicted road segments were deleted to reduce the storage cost. In terms of time, the statistical traffic speed model of different time intervals was constructed according to the periodic feature of the traffic condition to predict the required time for moving objects to enter the next section. And then the compression process was performed by deleting the road section information which predicted time error was smaller than the given threshold. In the comparison experiments with Paralleled Road-network-based trajectory comprESSion (PRESS) algorithm, the average compression ratio of CTPM was increased by 43% in space and 1.5% in time, and the temporal error was decreased by 9.5%. The experimental results show that the proposed algorithm can effectively reduce the compression time and compression error while improving the compression ratio.

Key words: time series data, spatio-temporal database, trajectory, trajectory compression, prediction model

摘要: 针对目前路网环境下海量轨迹数据压缩效率低下的问题,提出了一种基于预测模型的轨迹数据压缩方法(CTPM)。通过将轨迹数据的时间信息和空间信息分别进行压缩,使得压缩后的轨迹数据在空间维度上无损,并且在时间维度上误差有界,以此提高压缩效率。在空间方面,首先利用部分匹配预测(PPM)算法通过轨迹已经行驶的部分路段对其下一时刻可能的位置进行预测;然后通过删除预测成功的路段来减少轨迹数据的存储代价。在时间方面,首先利用轨迹通行状况具有周期性的特点,构建了不同时间区间的通行速度统计模型,来预测移动对象进入下一路段所需要的时间;然后删除预测时间误差小于给定阈值的路段数据来进行压缩处理。实验结果显示,与已有的基于路网的并行轨迹压缩(PRESS)算法相比,CTPM的空间压缩比和时间压缩比平均分别提高了43%和1.5%,同时时间压缩误差减小了9.5%。实验结果表明所提算法在提高压缩比的同时有效地降低了压缩时间和压缩误差。

关键词: 时序数据, 时空数据库, 轨迹, 轨迹压缩, 预测模型

CLC Number: