Parallel trajectory compression method based on MapReduce

doi:10.11772/j.issn.1001-9081.2017.05.1282

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (5): 1282-1286.DOI: 10.11772/j.issn.1001-9081.2017.05.1282

Previous Articles Next Articles

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).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP311

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

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

References

[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.

Parallel trajectory compression method based on MapReduce

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	QING Xinyi, CHEN Yuling, ZHOU Zhengqiang, TU Yuanchao, LI Tao. Blockchain storage expansion model based on Chinese remainder theorem [J]. Journal of Computer Applications, 2021, 41(7): 1977-1982.
[2]	DONG Cong, ZHANG Xiao, CHENG Wendi, SHI Jia. Performance optimization of distributed file system based on new type storage devices [J]. Journal of Computer Applications, 2020, 40(12): 3594-3603.
[3]	ZHANG Hang, LIU Shanzheng, TANG Dan, CAI Hongliang. Erasure code with low recovery-overhead in distributed storage systems [J]. Journal of Computer Applications, 2020, 40(10): 2942-2950.
[4]	ZHANG Guochao, WANG Ruijin. Blockchain shard storage model based on threshold secret sharing [J]. Journal of Computer Applications, 2019, 39(9): 2617-2622.
[5]	LI Yunshu, TENG Fei, LI Tianrui. Microoperation-based parameter auto-optimization method of Hadoop [J]. Journal of Computer Applications, 2019, 39(6): 1589-1594.
[6]	GUO Fangfang, CHAO Luomeng, ZHU Jianwen. Multi-source data parallel preprocessing method based on similar connection [J]. Journal of Computer Applications, 2019, 39(1): 57-60.
[7]	ZHENG Zhentao, ZHAO Zhuofeng, WANG Guiling, XU Yao. Ship trajectory extraction method for port parking area identification [J]. Journal of Computer Applications, 2019, 39(1): 113-117.
[8]	CAO Yunpeng, WANG Haifeng. Communication optimization for intermediate data of MapReduce computing model [J]. Journal of Computer Applications, 2018, 38(4): 1078-1083.
[9]	MA Youzhong, ZHANG Zhihui, LIN Chunjie. Research progress in similarity join query of big data [J]. Journal of Computer Applications, 2018, 38(4): 978-986.
[10]	ZHANG Chengchang, ZHANG Huayu, LUO Jianchang, HE Feng. Massive data analysis of power utilization based on improved K-means algorithm and cloud computing [J]. Journal of Computer Applications, 2018, 38(1): 159-164.
[11]	CHEN Yu, JIANG Wei, ZHOU Ji'en. Compression method for trajectory data based on prediction model [J]. Journal of Computer Applications, 2018, 38(1): 171-175.
[12]	ZHENG Linjang, LIU Xu, YI Bing. Dynamic weighted real-time map matching algorithm considering spatio-temporal property [J]. Journal of Computer Applications, 2017, 37(8): 2381-2386.
[13]	ZHOU Weibo, ZHONG Yong, LI Zhendong. Storage load balancing algorithm based on storage entropy [J]. Journal of Computer Applications, 2017, 37(8): 2209-2213.
[14]	LI Qiang, LIU Xiaofeng. Load balancing strategy of cloud storage based on Hopfield neural network [J]. Journal of Computer Applications, 2017, 37(8): 2214-2217.
[15]	MA Shengjun, CHEN Wanghu, YU Maoyi, LI Jinrong, JIA Wenbo. Analysis of factors affecting efficiency of data distributed parallel application in cloud environment [J]. Journal of Computer Applications, 2017, 37(7): 1883-1887.