Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (9): 1240-1249.DOI: 10.3778/j.issn.1673-9418.1507066

Previous Articles     Next Articles

Trajectory Compression Based on Moving Features

JIANG Junwen, ZHANG Kai, WANG Xiaoling+, JIN Cheqing   

  1. Institute for Data Science and Engineering, East China Normal University, Shanghai 200062, China
  • Online:2016-09-01 Published:2016-09-05

基于行驶特征的轨迹压缩技术

江俊文,张  凯,王晓玲+,金澈清   

  1. 华东师范大学 数据科学与工程研究院,上海 200062

Abstract: The popularity of mobile terminals and the development of global positioning system (GPS) produce mass of trajectory data. Based on the data, a lot of location-based services (LBS) provide services for people. However, the increment of trajectory data brings many challenges: huge data volume, long query latency, hard to analyze and data  redundancy. Hence the trajectory compression plays an important role for better LBS. This paper proposes a trajectory compression method which fully considers the moving features and handles trajectory as Markov sequence. The moving features include speed, direction and position. Gaussian distributionis used to model speed change, direction change and position distance, so that the status of the next point can be predicated well based on aforementioned information. According to the prediction accuracy, every point in trajectory is given a conditional self-information value. A compressed trajectory is generated by picking those points that satisfy the user-predefined value. Finally, this paper verifies the performance of the proposed compression method through a number of experiments on real datasets.

Key words: trajectory compression, moving features, self-information, Markov sequence

摘要: 移动终端的普及和全球定位系统(global positioning system,GPS)的发展,产生了海量的轨迹数据。许多基于位置的服务(location-based services,LBS)利用这些轨迹数据为用户提供服务。但是轨迹数据日益增多带来了许多挑战:数据量巨大,查询延时增长,数据分析困难以及数据冗余。轨迹压缩对于提供更好的服务是非常有必要的,因此提出了基于行驶特征的轨迹压缩技术,考虑了行驶特征,并且把轨迹数据建模为马尔可夫序列。行驶特征包括速度、方向和位置,使用高斯分布对速度变化、方向变化和位置距离进行建模,下一个点的状态就能通过之前的信息来进行预测;根据预测的准确度,为每个轨迹点赋予条件自信息量;筛选出满足用户设定准确度阈值的点,组成压缩后的轨迹。在真实数据集上进行了一系列的实验,证明了算法的性能。

关键词: 轨迹压缩, 行驶特征, 自信息量, 马尔可夫序列