Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (5): 1209-1212.DOI: 10.11772/j.issn.1001-9081.2015.05.1209

Previous Articles     Next Articles

Hybrid trajectory compression algorithm based on multiple spatiotemporal characteristics

WU Jiagao1,2, QIAN Keyu1,2, LIU Min1,2, LIU Linfeng1,2   

  1. 1. School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China;
    2. Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing Jiangsu 210003, China
  • Received:2014-12-08 Revised:2015-01-14 Online:2015-05-10 Published:2015-05-14

基于综合时空特性的混合式轨迹压缩算法

吴家皋1,2, 钱科宇1,2, 刘敏1,2, 刘林峰1,2   

  1. 1. 南京邮电大学 计算机学院, 南京 210003;
    2. 江苏省无线传感网高技术研究重点实验室, 南京 210003
  • 通讯作者: 吴家皋
  • 作者简介:吴家皋(1969-),男,江苏苏州人,副教授,博士,主要研究方向:移动社会网络、GIS应用; 钱科宇(1989-),男,江苏盐城人,硕士研究生,主要研究方向:移动计算; 刘敏(1988-),女,山东济宁人,硕士研究生,主要研究方向:移动模型; 刘林峰(1981-),男,江苏丹阳人,副教授,博士,主要研究方向:水下传感器网络.
  • 基金资助:

    国家自然科学基金资助项目(61373139);江苏省自然科学基金资助项目(BK2012833);南京邮电大学科研基金资助项目(NY213160).

Abstract:

In view of the problem that how to reduce the storage space of the trajectory data and improve the speed of data analysis and transmission in the Global Positioning System (GPS), a hybrid trajectory compression algorithm based on the multiple spatiotemporal characteristics was proposed in this paper. On the one hand, in the algorithm, a new online trajectory compression strategy based on the multiple spatiotemporal characteristics was adopted in order to choose the characteristic points more accurately by using the position, direction and speed information of GPS point. On the other hand, the hybrid trajectory compression strategy which combined online compression with batched compression was used, and the Douglas batched compression algorithm was adopted to do the second compression process of the hybrid trajectory compression. The experimental results show that the compression error of the new online trajectory compression strategy based on multiple spatiotemporal characteristics reduces significantly, although the compression ratio fells slightly compared with the existing spatiotemporal compression algorithm. By choosing appropriate cycle time of batching, the compression ratio and compression error of this algorithm are improved compared with the existing spatiotemporal compression algorithm.

Key words: Global Positioning System (GPS), trajectory compression, spatiotemporal characteristics, hybrid algorithm, Douglas algorithm

摘要:

针对车辆全球卫星定位系统(GPS)中如何降低轨迹数据存储空间,提高数据分析及传送速度等问题,提出一种基于综合时空特性的混合式轨迹压缩算法.该算法一方面采用了新的综合时空特性的在线轨迹压缩策略,利用GPS数据的位置信息、时间信息、方向角、速度信息进行轨迹特征点的综合判断,以更准确地选取特征点;另一方面,采用了在线与批处理相结合的混合式轨迹压缩策略,定时采用道格拉斯批量压缩算法对在线压缩的轨迹集进行二次压缩,以提高轨迹的压缩效率.实验结果表明,较现有的时空特性压缩算法,新的综合时空特性在线轨迹压缩策略虽然在压缩率上略有下降,但压缩误差有显著减小.进一步采用混合式压缩策略后,通过选取适当的批处理时间周期,所提算法在压缩率和压缩误差上较现有的时空特性算法均有所改进.

关键词: 全球卫星定位系统, 轨迹压缩, 时空特性, 混合式算法, 道格拉斯算法

CLC Number: