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

doi:10.11772/j.issn.1001-9081.2015.05.1209

计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1209-1212.DOI: 10.11772/j.issn.1001-9081.2015.05.1209

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

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

1. 南京邮电大学计算机学院, 南京 210003;
2. 江苏省无线传感网高技术研究重点实验室, 南京 210003

收稿日期:2014-12-08 修回日期:2015-01-14 发布日期:2015-05-14 出版日期:2015-05-10
通讯作者: 吴家皋
作者简介:吴家皋(1969-),男,江苏苏州人,副教授,博士,主要研究方向:移动社会网络、GIS应用; 钱科宇(1989-),男,江苏盐城人,硕士研究生,主要研究方向:移动计算; 刘敏(1988-),女,山东济宁人,硕士研究生,主要研究方向:移动模型; 刘林峰(1981-),男,江苏丹阳人,副教授,博士,主要研究方向:水下传感器网络.
基金资助:
国家自然科学基金资助项目(61373139);江苏省自然科学基金资助项目(BK2012833);南京邮电大学科研基金资助项目(NY213160).

Hybrid trajectory compression algorithm based on multiple spatiotemporal characteristics

WU Jiagao^1,2, QIAN Keyu^1,2, LIU Min^1,2, LIU Linfeng^1,2

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-14 Published:2015-05-10

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP393

吴家皋, 钱科宇, 刘敏, 刘林峰. 基于综合时空特性的混合式轨迹压缩算法[J]. 计算机应用, 2015, 35(5): 1209-1212.

WU Jiagao, QIAN Keyu, LIU Min, LIU Linfeng. Hybrid trajectory compression algorithm based on multiple spatiotemporal characteristics[J]. Journal of Computer Applications, 2015, 35(5): 1209-1212.

参考文献

[1] YUAN J, LUO J, YUE X. Principle and application of satellite navigation[M]. Beijing: China Astronautic Publishing House,2003:191-218.(袁建平,罗建军,岳晓奎.卫星导航原理与应用[M].北京:中国宇航出版社,2003:191-218.)
[2] PAN G, QI G, WU Z, et al. Land-use classification using taxi GPS traces[J]. IEEE Transactions on Intelligent Transportation System,2013,14(3):112-123.
[3] YAN Z. Towards semantic trajectory data analysis: a conceptual and computational approach[C]// Proceedings of the VLDB 2009 PhD Workshop Co-Located with the 35th International Conference on Very Large Data Bases. New York: ACM, 2009:81-83.
[4] HUNG C, PENG W. Model driven traffic data acquisition in vehicle sensor networks[C]// Proceedings of the 40th IEEE International Conference on Parallel Processing. Piscataway: IEEE, 2011: 424-432.
[5] LONG C, WONG R. Direction-preserving trajectory simplification[C]// VLDB 2013: International Conference on Very Large Data Bases. New York: ACM, 2013: 949-960.
[6] BELIMAN R. On the approximation of curves by line segments using dynamic programming [J]. Communications of the ACM, 1961,4(6):284.
[7] POTAMIAS M,PATROUMPAS K,SELLIS T. Sampling trajectory streams with spatiotemporal criteria[C]// Proceedings of the 18th International Conference on Scientific and Statistical Database Management. Piscataway: IEEE, 2006:275-284.
[8] BOGORNY V, VALIATI J, ALNARES L. Semantic-based pruning of redundant and uninteresting frequent geographic patterns[J]. GeoInformatica, 2010,14(2):201-220.
[9] DOUGLAS D H,PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973,10(2):112-122.
[10] CAO X, CONG G, JENSEN C S. Mining significant semantic locations from GPS data[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 1009-1020.
[11] ZHANG D, ZHANG X. A spatiotemporal compression algorithm for GPS trajectory data[J]. Journal of Traffic Information and Safety,2013,31(3):32-48.(张达夫,张析明.基于时空特性的GPS轨迹数据压缩算法[J].交通信息与安全,2013,31(3):32-48.).
[12] KEOGH E,CHU S,HART D, et al. An on-line algorithm for segmenting time series[C]// ICDM 2001: Proceedings of the 2001 IEEE International Conference on Data Mining. Piscataway: IEEE, 2001: 289-296.
[13] MERATNIA N, ROLF A. Spatiotemporal compression techniques for moving point objects[C]// Proceedings of the 9th International Conference on Extending Database Technology. Berlin: Springer, 2004:765-782.

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

Hybrid trajectory compression algorithm based on multiple spatiotemporal characteristics

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	杨博, 段宗涛, 左鹏飞, 肖媛媛, 王艺霖. 融合异构交通态势的事故预测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3625-3631.
[2]	邓亮亮, 张立臣, 姜文超. 基于对象时空Petri网的CPS建模与仿真[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3334-3339.
[3]	王海起, 王志海, 李留珂, 孔浩然, 王琼, 徐建波. 基于网格划分的城市短时交通流量时空预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2274-2280.
[4]	陈煜, 蒋伟, 周继恩. 基于预测模型的轨迹数据压缩方法[J]. 计算机应用, 2018, 38(1): 171-175.
[5]	郑林江, 刘旭, 易兵. 考虑时空特性的动态权重实时地图匹配算法[J]. 计算机应用, 2017, 37(8): 2381-2386.
[6]	吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37(5): 1282-1286.
[7]	范东溟于建国. 林火巡护与扑救车载定位系统设计[J]. 计算机应用, 2012, 32(11): 3251-3261.
[8]	李会英曹凯王晓原. 道路线形特征自动分类方法[J]. 计算机应用, 2011, 31(06): 1692-1695.
[9]	盛秀杰李宏利陶伟亮朱虹靖肖成材李楠楠. 基于数据字典的导航地图质量检测软件[J]. 计算机应用, 2010, 30(4): 1121-1124.