基于MapReduce的轨迹压缩并行化方法

doi:10.11772/j.issn.1001-9081.2017.05.1282

计算机应用 ›› 2017, Vol. 37 ›› Issue (5): 1282-1286.DOI: 10.11772/j.issn.1001-9081.2017.05.1282

基于MapReduce的轨迹压缩并行化方法

吴家皋^1,2, 夏轩¹, 刘林峰^1,2

1. 南京邮电大学计算机学院, 南京 210003;
2. 计算机网络和信息集成教育部重点实验室(东南大学), 南京 211189

收稿日期:2016-11-07 修回日期:2016-12-14 出版日期:2017-05-10 发布日期:2017-05-16
通讯作者: 吴家皋
作者简介:吴家皋(1969-),男,江苏苏州人,副教授,博士,CCF会员,主要研究方向:移动网络、云计算;夏轩(1989-),男,江苏宿迁人,硕士研究生,主要研究方向:云计算、移动模型;刘林峰(1980-),男,江苏丹阳人,副教授,博士,CCF会员,主要研究方向:水下传感器网络。
基金资助:
国家自然科学基金资助项目（61373139，41571389，71301081）；东南大学计算机网络和信息集成教育部重点实验室开放基金资助项目（K93-9-2014-05B）；南京邮电大学科研基金资助项目（NY214063）。

Parallel trajectory compression method based on MapReduce

WU Jiagao^1,2, XIA Xuan¹, LIU Linfeng^1,2

1. School of Computer, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003, China;
2. Key Laboratory of Computer Network and Information Integration of Ministry of Education(Southeast University), Nanjing Jiangsu 211189, China

Received:2016-11-07 Revised:2016-12-14 Online:2017-05-10 Published:2017-05-16
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61373139,41571389,71301081), the Open Research Fund from Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, China (K93-9-2014-05B), the Scientific Research Foundation of Nanjing University of Posts and Telecommunications (NY214063).

摘要/Abstract

摘要： 带有全球定位系统（GPS）功能设备的增多，产生大量的时空轨迹数据，给数据的存储、传输和处理带来了沉重的负担。为了减轻这种负担，各种轨迹压缩方法也随之产生。提出了一种基于MapReduce的并行化轨迹压缩方法，针对并行化导致的分段点前后轨迹的相关性被破坏的问题，首先，采用两种分段点相互交错的划分方法划分轨迹；然后，将分段轨迹分配到多个节点上进行并行化压缩；最后，对压缩结果进行匹配合并。性能测试分析结果表明，所提出的并行化轨迹压缩方法能够大幅提高压缩效率，而且能完全消除因分段导致分段点前后相关性被破坏带来的误差。

关键词: 轨迹压缩, 分布式存储, MapReduce, Hadoop, 全球定位系统轨迹

Abstract: The massive spatiotemporal trajectory data is a heavy burden to store, transmit and process, which is caused by the increase Global Positioning System (GPS)-enable devices. In order to reduce the burden, many kinds of trajectory compression methods were generated. A parallel trajectory compression method based on MapReduce was proposed in this paper. In order to solve the destructive problem of correlation nearby segmentation points caused by the parallelization, in this method, the trajectory was divided by two segmentation methods in which the segmentation points were interleaving firstly. Then, the trajectory segments were assigned to different nodes for parallel compression. Lastly, the compression results were matched and merged. The performance test and analysis results show that the proposed method can not only increase the compression efficiency significantly, but also eliminate the error which is caused by the destructive problem of correlation.

Key words: trajectory compression, distributed storage, MapReduce, Hadoop, Global Positioning System (GPS) trajectory

中图分类号:

TP311

吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37(5): 1282-1286.

WU Jiagao, XIA Xuan, LIU Linfeng. Parallel trajectory compression method based on MapReduce[J]. Journal of Computer Applications, 2017, 37(5): 1282-1286.

参考文献

[1] WEI H, WANG Y, FORMAN G, et al. Fast Viterbi map matching with tunable weight functions[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York:ACM, 2012:613-616.
[2] MIWA T, KIUCHI D, YAMAMOTO T, et al. Development of map matching algorithm for low frequency probe data[J]. Transportation Research Part C:Emerging Technologies, 2012, 22(5):132-145.
[3] 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.
[4] GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google file system[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5):29-43.
[5] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113.
[6] YANG H, DASDAN A, HSIAO R L, et al. Map-reduce-merge:simplified relational data processing on large clusters[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2007:1029-1040.
[7] ISARD M, BUDIU M, YU Y, et al. Dryad:distributed data-parallel programs from sequential building blocks[J]. ACM SIGOPS Operating Systems Review, 2007, 41(3):59-72.
[8] OLSTON C, REED B, SRIVASTAVA U, et al. Pig latin:a not-so-foreign language for data processing[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:1099-1110.
[9] KELLARIS G, PELEKIS N, THEODORIDIS Y. Trajectory compression under network constraints[C]//Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases. Berlin:Springer, 2009:392-398.
[10] GOTSMAN R, KANZA Y. Compact representation of GPS trajectories over vectorial road networks[C]//Proceedings of the 13th International Symposium Advances in Spatial and Temporal Databases. Berlin:Springer-Verlag, 2013:241-258.
[11] 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. San Francisco, CA:Morgan Kaufmann, 2009:1-6.
[12] SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A conceptual view on trajectories[J]. Data & Knowledge Engineering, 2008, 65(1):126-146.
[13] MERATNIA N, BY R A D. Spatiotemporal compression techniques for moving point objects[C]//Proceedings of the 9th International Conference on Extending Database Technology. Berlin:Springer, 2004:765-782.
[14] 张达夫, 张昕明. 基于时空特性的GPS轨迹数据压缩算法[J]. 交通信息与安全, 2013, 31(3):6-9.(ZHANG D F, ZHANG X M. GPS trajectory data compression algorithm based on the characteristics of time and space[J].Traffic Information and Security,2013,31(3):6-9.)
[15] SUN P, XIA S, YUAN G, et al. An overview of moving object trajectory compression algorithms[J]. Mathematical Problems in Engineering, 2016, 2016(3):1-13.
[16] KEOGH E, CHU S, HART D, et al. An online algorithm for segmenting time series[C]//Proceedings of the 2001 IEEE International Conference on Data Mining. Piscataway, NJ:IEEE, 2001:289-296.
[17] 吴家皋, 刘敏, 韦光, 等. 一种改进的滑动窗口轨迹数据压缩算法[J]. 计算机技术与发展, 2015, 25(12):47-51.(WU J G, LIU M, WEI G, et al. An improved trajectory data compression algorithm of sliding window[J]. Computer Technology and Development, 2015, 25(12):47-51.)
[18] HUANG J, QIAO S, YU H, et al. Parallel map matching on massive vehicle GPS data using MapReduce[C]//Proceedings of the 2013 IEEE 10th International Conference on High Performance Computing and Communications. Piscataway, NJ:IEEE, 2013:1498-1503.
[19] LI D, HAITAO Y, ZHOU X, et al. Map-Reduce for calibrating massive bus trajectory data[C]//Proceedings of the 201313th International Conference on ITS Telecommunications. Piscataway, NJ:IEEE, 2013:44-49.
[20] HU C, KANG X, LUO N, et al. Parallel clustering of big data of spatio-temporal trajectory[C]//Proceedings of the 201511th International Conference on Natural Computation. Piscataway, NJ:IEEE, 2015:769-774.

基于MapReduce的轨迹压缩并行化方法

Parallel trajectory compression method based on MapReduce

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	卿欣艺, 陈玉玲, 周正强, 涂园超, 李涛. 基于中国剩余定理的区块链存储扩展模型[J]. 计算机应用, 2021, 41(7): 1977-1982.
[2]	董聪, 张晓, 程文迪, 石佳. 基于新型存储器件的分布式文件系统性能优化[J]. 计算机应用, 2020, 40(12): 3594-3603.
[3]	张航, 刘善政, 唐聃, 蔡红亮. 分布式存储系统中的低修复成本纠删码[J]. 计算机应用, 2020, 40(10): 2942-2950.
[4]	张国潮, 王瑞锦. 基于门限秘密共享的区块链分片存储模型[J]. 计算机应用, 2019, 39(9): 2617-2622.
[5]	李耘书, 滕飞, 李天瑞. 基于微操作的Hadoop参数自动调优方法[J]. 计算机应用, 2019, 39(6): 1589-1594.
[6]	郭方方, 潮洛蒙, 朱建文. 基于相似连接的多源数据并行预处理方法[J]. 计算机应用, 2019, 39(1): 57-60.
[7]	郑振涛, 赵卓峰, 王桂玲, 徐垚. 面向港口停留区域识别的船舶停留轨迹提取方法[J]. 计算机应用, 2019, 39(1): 113-117.
[8]	马友忠, 张智辉, 林春杰. 大数据相似性连接查询技术研究进展[J]. 计算机应用, 2018, 38(4): 978-986.
[9]	曹云鹏, 王海峰. 面向MapReduce计算模式的中间数据通信优化[J]. 计算机应用, 2018, 38(4): 1078-1083.
[10]	张承畅, 张华誉, 罗建昌, 何丰. 基于云计算和改进K-means算法的海量用电数据分析方法[J]. 计算机应用, 2018, 38(1): 159-164.
[11]	陈煜, 蒋伟, 周继恩. 基于预测模型的轨迹数据压缩方法[J]. 计算机应用, 2018, 38(1): 171-175.
[12]	周渭博, 钟勇, 李振东. 基于存储熵的存储负载均衡算法[J]. 计算机应用, 2017, 37(8): 2209-2213.
[13]	李强, 刘晓峰. 基于Hopfield神经网络的云存储负载均衡策略[J]. 计算机应用, 2017, 37(8): 2214-2217.
[14]	郑林江, 刘旭, 易兵. 考虑时空特性的动态权重实时地图匹配算法[J]. 计算机应用, 2017, 37(8): 2381-2386.
[15]	马生俊, 陈旺虎, 俞茂义, 李金溶, 郏文博. 云环境下影响数据分布并行应用执行效率的因素分析[J]. 计算机应用, 2017, 37(7): 1883-1887.