计算机科学 ›› 2020, Vol. 47 ›› Issue (10): 102-107.doi: 10.11896/jsjkx.191000194
励益韬, 孙未未
LI Yi-tao, SUN Wei-wei
摘要: 随着定位技术和存储技术的发展,海量的轨迹被人类记录。如何有效地压缩轨迹中最被人关注的空间路径信息并无损地将原始信息还原,引起了人们的广泛关注。轨迹压缩算法主要分为基于简化线段的压缩和基于路网的轨迹压缩两类,现有算法存在算法假设不合理、压缩能力差等缺点。文中根据路网中轨迹的分布特性以及循环神经网络对变长时序序列的建模能力,提出了基于循环神经网络的轨迹压缩算法,通过深度学习模型高效地概括轨迹分布,同时利用路网结构进一步缩小压缩空间,定量分析了不同输入对算法压缩比的影响。最后通过实验证明,基于循环神经网络的轨迹压缩算法不仅具有比现有算法更高的压缩比,还能支持未经过训练的轨迹数据的压缩;同时验证了终点信息如何对算法压缩比产生影响的假设。
中图分类号:
[1]ZHENG Y.Trajectory Data Mining:An Overview[J].ACM Transactions on Intelligent Systems and Technology,2015,6(3):1-41. [2]HAN H Y,SUN W W,ZHENG B H.COMPRESS:A Comprehensive Framework of Trajectory Compression in Road Networks[J].ACM Transactions on Database Systems,2017,42(2):1-49. [3]WU H,CHEN Z Y,SUN W W,et al.Modeling trajectories with recurrent neural networks[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI’17).AAAI Press. [4]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. [5]CAO H,WOLFSON O.Nonmaterialized motion information in transport networks[M]//Database Theory - ICDT 2005.Berlin:Springer,2005. [6]LERIN P M,YAMAMOTO D,TAKAHASHI N.Encodingtravel traces by using road networks and routing algorithms[M]//Intelligent Interactive Multimedia:Systems and Services.Berlin:Springer,2012. [7]KELLARIS G,PELEKIS N,THEODORIDIS Y.Map-matched trajectory compression[J].Journal of Systems & Software,2013,86(6):1566-1579. [8]SONG R,SUN W,ZHENG B,et al.PRESS:a novel framework of trajectory compression in road networks[J].Proceedings of the Vldb Endowment,2014,7(9):661-672. [9]KOIDE S,TADOKORO Y,XIAO C,et al.CiNCT:compression and retrieval for massive vehicular trajectories via relative movement labeling[C]//IEEE International Conference on Data Engineering (ICDE2018).IEEE,2017. [10]ZHENG J C,NI L M.Modeling heterogeneous routing decisions in trajectories for driving experience learning[C]//UbiComp. New York,USA:ACM Press,2014:951-961. [11]ZIEBART B D,MAAS A L,DEY A K,et al.Navigate like a cabbie:probabilistic reasoning from observed context-aware behavior[C]//International Conference on Ubiquitous Computing.ACM,2008. [12]WU H,MAO J Y,SUN W W,et al.Probabilistic robust route recovery with spatio-temporal dynamics[C]//Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.ACM,2016. [13]HOCHREITER S,SCHMIDHUBER J.Long short-term memory[J].Neural Computation,1997,9(8):1735-1780. [14]RAYMOND R,MORIMURA T,OSOGAMI T,et al.Map matching with hidden markov model on sampled road network[C]//International Conference on Pattern Recognition.2012. [15]ZHENG Y.Map-matching for low-sampling-rate gps trajectories[C]//Acm Sigspatial International Symposium on Advances in Geographic Information Systems.DBLP,2009. [16]ZHANG H Y,WU H,SUN W W,et al.Deeptravel:a neural network based travel time estimation model with auxiliary supervision[J].arXiv:1802.02147,2018. [17]WU J G,QIAN K Y,LIU M,et al.Hybrid trajectory compression algorithm based on multiple spatiotemporal characteristics[J].Journal of Computer Applications,2015,35(5):1209-1212. [18]SHAN Z Q,WU H,SUN W W,et al.COBWEB:a robust map update system using GPS trajectories[C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing.ACM,2015. [19]MIKOLOV T,SUTSKEVER I,CHEN K,et al.Distributed representations of words and phrases and their compositionality[J].Advances in Neural Information Processing Systems,2013,26:3111-3119. [20]LUO W M,TAN H Y,CHEN L,et al.Finding time period-based most frequent path in big trajectory data[C]//Procee-dings of the 2013 ACM SIGMOD International Conference on Management of Data.ACM,2013. |
[1] | 饶志双, 贾真, 张凡, 李天瑞. 基于Key-Value关联记忆网络的知识图谱问答方法 Key-Value Relational Memory Networks for Question Answering over Knowledge Graph 计算机科学, 2022, 49(9): 202-207. https://doi.org/10.11896/jsjkx.220300277 |
[2] | 汤凌韬, 王迪, 张鲁飞, 刘盛云. 基于安全多方计算和差分隐私的联邦学习方案 Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy 计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108 |
[3] | 徐涌鑫, 赵俊峰, 王亚沙, 谢冰, 杨恺. 时序知识图谱表示学习 Temporal Knowledge Graph Representation Learning 计算机科学, 2022, 49(9): 162-171. https://doi.org/10.11896/jsjkx.220500204 |
[4] | 王剑, 彭雨琦, 赵宇斐, 杨健. 基于深度学习的社交网络舆情信息抽取方法综述 Survey of Social Network Public Opinion Information Extraction Based on Deep Learning 计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099 |
[5] | 郝志荣, 陈龙, 黄嘉成. 面向文本分类的类别区分式通用对抗攻击方法 Class Discriminative Universal Adversarial Attack for Text Classification 计算机科学, 2022, 49(8): 323-329. https://doi.org/10.11896/jsjkx.220200077 |
[6] | 姜梦函, 李邵梅, 郑洪浩, 张建朋. 基于改进位置编码的谣言检测模型 Rumor Detection Model Based on Improved Position Embedding 计算机科学, 2022, 49(8): 330-335. https://doi.org/10.11896/jsjkx.210600046 |
[7] | 孙奇, 吉根林, 张杰. 基于非局部注意力生成对抗网络的视频异常事件检测方法 Non-local Attention Based Generative Adversarial Network for Video Abnormal Event Detection 计算机科学, 2022, 49(8): 172-177. https://doi.org/10.11896/jsjkx.210600061 |
[8] | 侯钰涛, 阿布都克力木·阿布力孜, 哈里旦木·阿布都克里木. 中文预训练模型研究进展 Advances in Chinese Pre-training Models 计算机科学, 2022, 49(7): 148-163. https://doi.org/10.11896/jsjkx.211200018 |
[9] | 周慧, 施皓晨, 屠要峰, 黄圣君. 基于主动采样的深度鲁棒神经网络学习 Robust Deep Neural Network Learning Based on Active Sampling 计算机科学, 2022, 49(7): 164-169. https://doi.org/10.11896/jsjkx.210600044 |
[10] | 苏丹宁, 曹桂涛, 王燕楠, 王宏, 任赫. 小样本雷达辐射源识别的深度学习方法综述 Survey of Deep Learning for Radar Emitter Identification Based on Small Sample 计算机科学, 2022, 49(7): 226-235. https://doi.org/10.11896/jsjkx.210600138 |
[11] | 彭双, 伍江江, 陈浩, 杜春, 李军. 基于注意力神经网络的对地观测卫星星上自主任务规划方法 Satellite Onboard Observation Task Planning Based on Attention Neural Network 计算机科学, 2022, 49(7): 242-247. https://doi.org/10.11896/jsjkx.210500093 |
[12] | 胡艳羽, 赵龙, 董祥军. 一种用于癌症分类的两阶段深度特征选择提取算法 Two-stage Deep Feature Selection Extraction Algorithm for Cancer Classification 计算机科学, 2022, 49(7): 73-78. https://doi.org/10.11896/jsjkx.210500092 |
[13] | 程成, 降爱莲. 基于多路径特征提取的实时语义分割方法 Real-time Semantic Segmentation Method Based on Multi-path Feature Extraction 计算机科学, 2022, 49(7): 120-126. https://doi.org/10.11896/jsjkx.210500157 |
[14] | 祝文韬, 兰先超, 罗唤霖, 岳彬, 汪洋. 改进Faster R-CNN的光学遥感飞机目标检测 Remote Sensing Aircraft Target Detection Based on Improved Faster R-CNN 计算机科学, 2022, 49(6A): 378-383. https://doi.org/10.11896/jsjkx.210300121 |
[15] | 王建明, 陈响育, 杨自忠, 史晨阳, 张宇航, 钱正坤. 不同数据增强方法对模型识别精度的影响 Influence of Different Data Augmentation Methods on Model Recognition Accuracy 计算机科学, 2022, 49(6A): 418-423. https://doi.org/10.11896/jsjkx.210700210 |
|