轨迹数据压缩综述

doi:10.3969/j.issn.1000-5641.2015.00.005

摘要/Abstract

摘要： 移动终端的普及和全球定位系统（Global Positioning System,GPS）的发展，产生了海量的移动轨迹数据.许多基于位置服务(LocationBased Services,LBS)利用这些轨迹数据为用户提供服务.但是轨迹数据的日益增多也带来了许多挑战：数据量巨大、查询延时增长、数据冗余.因此，轨迹压缩对于提供更好的服务是非常有必要的.轨迹压缩的目标是在满足压缩轨迹与原始轨迹之间的相似度条件下，尽可能减小轨迹数据量.本文回顾了已有的轨迹压缩工作，包括线段简化压缩方法、基于路网的压缩方法和语义压缩方法，并介绍了基于压缩轨迹的查询处理和轨迹管理系统.

关键词: 轨迹数据, 压缩, 查询, 管理, 压缩率

Abstract: The popularity of mobile terminals and the development of GPS positioning technology produce a mass of mobile 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 and data redundancy. Hence the trajectory compression plays an important role in providing better LBS. The purpose of trajectory compression is to minimize the size of trajectory as far as possible, which satisfies the threshold of similarity between compressed trajectory and original trajectory. This paper aims at illustrating useful trajectory compression methods, including line simplification methods, mapmatching based compression methods and semantic compression methods, and introducing query processing of compressed trajectories and trajectory management systems.

Key words: trajectory data, compression, query, management, compression rate

中图分类号:

TP391

江俊文,王晓玲. 轨迹数据压缩综述[J]. 华东师范大学学报(自然科学版), 2015, 2015(5): 61-76.

JIANG Jun-wen,WANG Xiao-ling. Review on trajectory data compression[J]. Journal of East China Normal University(Natural Sc, 2015, 2015(5): 61-76.

参考文献

［1］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.

［2］KEOGH E, CHU S, HART D, et al. An online algorithm for segmenting time series［C］Proceedings of the IEEE International Conference on Data Mining. IEEE, 2001: 289296.

［3］POTAMIAS M, PATROUMPAS K, SELLIS T. Sampling trajectory streams with spatiotemporal criteria［C］Proceedings of the 18th IEEE International Conference on Scientific and Statistical Database Management. IEEE, 2006: 275284.

［4］LERIN P M, YAMAMOTO D, Takahashi N. Encoding travel traces by using road networks and routing algorithms［M］Intelligent Interactive Multimedia: Systems and Services. Berlin: Springer, 2012: 233243. 

［5］KELLARIS G, PELEKIS N, THEODORIDIS Y. Trajectory compression under network constraints［M］Advances in Spatial and Temporal Databases. Berlin: Springer, 2009: 392398.

［6］KELLARIS G, PELEKIS N, THEODORIDIS Y. Mapmatched trajectory compression［J］. Journal of Systems and Software, 2013, 86(6): 15661579.

［7］SONG R, SUN W, ZHENG B, et al. PRESS: A novel framework of trajectory compression in road networks［C］Proceedings of the 40th International Conference on Very Large Data Bases. ACM, 2014: 14021546.

［8］MUCKELL J, HWANG J H, LAWSON C T, et al. Algorithms for compressing GPS trajectory data: An empirical evaluation［C］Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010: 402405.

［9］SCHMID F, RICHTER K F, LAUBE P. Semantic trajectory compression［M］Advances in Spatial and Temporal Databases. Berlin: Springer, 2009: 411416.

［10］RICHTER K F, SCHMID F, LAUBE P. Semantic trajectory compression: Representing urban movement in a nutshell［J］. Journal of Spatial Information Science, 2014 (4): 330.

［11］YAN Z, SPACCAPIETRA S. Towards semantic trajectory data analysis: A conceptual and computational approach［C］Proceedings of the International Conference on Very Large Data Bases PhD Workshop. 2009:16.

［12］DAMIANI M L, SPACCAPIETRA S, PARENT C, et al. A conceptual view on trajectories［J］. Data and Knowledge Engineering, 2008, 65(1):126146.

［13］HERSHBERGER J E, SNOEYINK J. Speeding up the douglaspeucker linesimplification algorithm［M］International Symposium on Spatial Data Handling. Berlin: Springer, 1992:134143.

［14］MERATNIA N, ROLF A. Spatiotemporal compression techniques for moving point objects［M］Advances in Database Technology. Berlin: Springer, 2004: 765782.

［15］LIU J, ZHAO K, SOMMER P, et al. Bounded quadrant system: Errorbounded trajectory compression on the go［C］Proceedings of the 31st IEEE International Conference on Data Engineering. IEEE, 2015: 987998.

［16］MUCKELL J, HWANG J H, PATIL V, et al. SQUISH: An online approach for GPS trajectory compression［C］Proceedings of the 2nd International Conference on Computing for Geospatial Research and Applications. ACM, 2011: 18.

［17］MUCKELL J, OLSEN P W, HWANG J H, et al. Compression of trajectory data: A comprehensive evaluation and new approach［J］. Geoinformatica, 2014, 18(3):435460.

［18］BRAKATSOULAS S, PFOSER D, SALAS R, et al. On mapmatching vehicle tracking data［C］Proceedings of the 31st International Conference on Very Large Data Bases. ACM, 2005: 853864.

［19］HU C, WOLFSON O. Nonmaterialized motion information in transport networks［C］Proceedings of the 10th International Conference on Database Theory. 2005:173188.

［20］YIN H, WOLFSON O. A weightbased map matching method in moving objects databases［C］Proceedings of the IEEE International Conference on Scientific and Statistical Database Management. IEEE, 2004: 437438.

［21］SU H, ZHENG K, ZENG K, et al. STMaker—A system to make sense of trajectory data［C］Proceedings of the 40th International Conference on Very Large Data Bases. ACM, 2014:17011704.

［22］SU H, ZHENG K, ZENG K, et al. Making sense of trajectory data: A partitionandsummarization approach［C］Proceedings of the 31st IEEE International Conference on Data Engineering. IEEE, 2015: 963974.

［23］ZHENG Y, ZHOU X. Computing with Spatial Trajectories［M］. Berlin: Springer, 2011.

［24］CHEN L, ZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories［C］Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. ACM, 2005: 491502.

［25］CHEN Z, SHEN H T, ZHOU X, et al. Monitoring path nearest neighbor in road networks［C］Proceedings of the 35th SIGMOD International Conference on Management of Data. 2009:591602.

［26］SHANG S, DENG K, XIE K. Best point detour query in road networks［C］Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010: 7180.

［27］PFOSER D, JENSEN C S, THEODORIDIS Y. Novel approaches in query processing for moving object trajectories［C］Proceedings of the 26th International Conference on Very Large Data Bases. ACM, 2000: 395406.

［28］FRENTZOS E, GRATSIAS K, PELEKIS N, et al. Algorithms for nearest neighbor search on moving object trajectories［J］. Geoinformatica, 2007, 11(2):159193.

［29］CHEN Z, SHEN H T, ZHOU X, et al. Searching trajectories by locations: An efficiency study［C］Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM, 2010: 255266.

［30］LEE J G, HAN J, WHANG K Y. Trajectory clustering: A partitionandgroup framework［C］Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. ACM, 2007: 593604.

［31］JEUNG H, YIU M L, ZHOU X F, et al. Discovery of convoys in trajectory databases［C］Proceedings of the 34th International Conference on Very Large Data Bases. ACM, 2008: 10681080.

［32］LEE J, HAN J, LI X, et al. TraClass: Trajectory classification using hierarchical regionbased and trajecorybased clustering［C］Proceedings of the 34th International Conference on Very Large Data Bases. 2008: 10811094.

［33］CONG G, LU H, OOI B C, et al. Efficient spatial keyword search in trajectory databases［R/OL］. arXiv:1205.2880v1.

［34］CHEN L, CONG G, JENSEN C S, et al. Spatial keyword query processing: An experimental evaluation［C］Proceedings of the 39th International Conference on Very Large Data Bases. ACM, 2013: 217228.

［35］CARY A, WOLFSON O, RISHE N. Efficient and scalable method for processing topk spatial boolean queries［M］Scientific and Statistical Database Management. Heidelberg: Springer, 2010: 8795.

［36］CONG G, JENSEN C S, WU D. Efficient retrieval of the topk most relevant spatial web objects［C］Proceedings of the 35th International Conference on Very Large Data Bases. ACM, 2009: 337348.

［37］LI Z, LEE K C K, ZHENG B, et al. An efficient index for geographic document search［J］. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(4): 585599.

［38］WU D, MAN L Y, CONG G, et al. Joint topk spatial keyword query processing［J］. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(10): 19891903.

［39］KHODAEI A, SHAHABI C, LI C. Hybrid indexing and seamless ranking of spatial and textual features of web documents［J］. Lecture Notes in Computer Science, 2010: 450466.

［40］VAID S, JONES C B, JOHO H, et al. Spatiotextual indexing for geographical search on the web［C］Proceedings of the 9th Symposium on Spatial and Temporal Databases. 2005: 218235.

［41］WU D, YIU M L, JENSEN C S, et al. Efficient continuously moving topk spatial keyword query processing［C］Proceedings of the 27th International Conference on Data Engineering. 2011: 541552.

［42］ZHOU Y, XIE X, WANG C, et al. Hybrid index structures for locationbased web search［C］Proceedings of the 14th ACM international conference on Information and Knowledge Management. ACM, 2005: 155162.

［43］CUDREMAUROUX P, WU E, MADDEN S. TrajStore: An adaptive storage system for very large trajectory data sets［C］Proceedings of the 26th IEEE International Conference on Data Engineering. IEEE, 2010: 109120.

［44］WU E, CUDREMAUROUX P, MADDEN S. Demonstration of the trajStore system［C］Proceedings of the 35th International Conference on Very Large Data Bases. ACM, 2009: 15541557.

［45］WANG H, ZHENG K, XU J, et al. Sharkdb: An inmemory columnoriented trajectory storage［C］Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. ACM, 2014: 14091418.

［46］NISHIMURA S, DAS S, AGRAWAL D, et al. MDHBase: A scalable multidimensional data infrastructure for location aware services［C］Proceedings of the 12th IEEE International Conference on Mobile Data Management. IEEE, 2011: 716.

［47］HUANG S, WANG B, ZHU J Y, et al. RHBase: A multidimensional indexing framework for cloud computing environment［C］Proceedings of the 14th IEEE International Conference on Data Mining Workshops. IEEE, 2014: 569574.

［48］ELDAWY A, MOKBEL M F. A demonstration of SpatialHadoop: An efficient mapReduce framework for spatial data［J］. Proceedings of the 39th International Conference on Very Large Data Bases. ACM, 2013: 12301233.

［49］ELDAWY A. SpatialHadoop: Towards flexible and scalable spatial processing using mapreduce［C］Proceedings of the SIGMOD PhD Symposium. ACM, 2014: 4650.

[1]	赵红成, 田秀霞, 杨泽森, 白万荣. YOLO-S: 一种新型轻量的安全帽佩戴检测模型[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 134-145.
[2]	方创新, 宋浩, 林煜明, 周娅. CPU-GPU异构环境下的大规模商品知识查询处理[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 157-168.
[3]	邓思佳, 佟兴, 唐海波, 张召, 金澈清. 面向区块链的数据管理中间件[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 60-73.
[4]	项兆坤, 陈婷, 苏仟, 张蓉. 面向OLAP数据库查询处理功能的模糊测试工具[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 74-83.
[5]	国晓春, 韩镇阳, 卢少勇, 郑丙辉, 田泽斌. 太湖流域工业点源排污许可管理技术集成与应用研究[J]. 华东师范大学学报（自然科学版）, 2021, 2021(4): 39-45.
[6]	赖叶静, 郝珊锋, 黄定江. 深度神经网络模型压缩方法与进展[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 68-82.
[7]	罗祖奎, 李扬, 徐曦, 屈铭志, 马进, 孙文, 黄舒欣, 仝慧林. 江苏省沉海圩乡村湿地水稻田种植模式转变后的生态恢复效果[J]. 华东师范大学学报（自然科学版）, 2020, 2020(4): 164-172.
[8]	黄皓, 李志方, 王嘉伦, 翁楚良. 基于GPU的关系型流处理系统实现与优化[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 178-189.
[9]	殷佳玲, 夏帆, 顾航, 祝翔, 孙晨, 王晔, 董启文, 宋树彬, 傅云斌. 基于微服务的研究生培养系统的设计与实现[J]. 华东师范大学学报(自然科学版), 2019, 2019(4): 83-96.
[10]	李艳丽, 张宗勇, 冯捷, 李志辉. 一种分布式可视化Dubbo接口测试平台[J]. 华东师范大学学报(自然科学版), 2019, 2019(4): 120-132,143.
[11]	刘娜娜, 郭雪艳, 崔易翀, 张红, 陆俊尧, 达良俊. 上海城市公园夜间延长开放服务需求与管理对策[J]. 华东师范大学学报(自然科学版), 2019, 2019(3): 155-163.
[12]	廖瑜欣, 张勇, 古润竹. 用水效率目标约束下的省市用水差异及分区对策探讨[J]. 华东师范大学学报(自然科学版), 2019, 2019(1): 136-143.
[13]	唐海波, 林煜明, 李优. 一种基于K-Means的平衡约束聚类算法[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 164-171.
[14]	潘宇晨, 李宇明, 张春熙, 张蓉, 洪道诚. 基于分布式数据库Cedar的高效工单管理系统设计与实现[J]. 华东师范大学学报(自然科学版), 2018, 2018(3): 88-96.
[15]	顾航, 夏帆, 宋树彬, 肖李敏, 董启文, 徐林昊, 周傲英. 研究生信息平台中权限管理的设计与实现[J]. 华东师范大学学报(自然科学版), 2018, 2018(3): 109-120.