Computer Science ›› 2020, Vol. 47 ›› Issue (10): 102-107.doi: 10.11896/jsjkx.191000194

• Database & Big Data & Data Science • Previous Articles     Next Articles

Trajectory Compression Algorithm Based on Recurrent Neural Network

LI Yi-tao, SUN Wei-wei   

  1. School of Computer Science,Fudan University,Shanghai 201203,China
    Shanghai Key Laboratory of Data Science,Fudan University,Shanghai 201203,China
  • Received:2019-10-29 Revised:2019-12-18 Online:2020-10-15 Published:2020-10-16
  • About author:LI Yi-tao,born in 1994,postgraduate.His main research interests include spatiotemporal data mining and so on.
    SUN Wei-wei,born in 1973,Ph.D,professor,is a senior member of China Computer Federation.His main research interests include big spatiotemporal data and so on.
  • Supported by:
    National Natural Science Foundation of China (61772138) and National Key Research and Development Program of China (2019YFB1704400)

Abstract: With the development of positioning technology and storage technology,massive trajectories have been recorded by humans.How to effectively compress the most interesting spatial path information in the trajectory and how to restore the original information has caused extensive research.The compression algorithm for trajectories is mainly divided into line-simplified compression and road-based trajectory compression.Existing algorithms have shortcomings such as unreasonable algorithm assumptions and poor compression capability.According to the distribution characteristics of trajectories in the road network and the probabilistic modeling ability of recurrent neural networks for variable-length time series,a trajectory compression algorithm based on recurrent neural network is proposed.The trajectory distribution is efficiently summarized by our algorithm,in which the compression space is further reduced by the road network structure.Meanwhile,the influence of different input on the compression ratio of the algorithm is quantitatively analyzed.Finally,the experiment proves that the trajectory compression algorithm based on recurrent neural network not only has a higher compression ratio than existing algorithms,but also supports the compression of untrained trajectory data,and demonstrates the compression ratio of the algorithm can be improved by using the time information.

Key words: Deep learning, Modeling trajectory, Recurrent neural network, Trajectory compression

CLC Number: 

  • TP301
[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] XU Yong-xin, ZHAO Jun-feng, WANG Ya-sha, XIE Bing, YANG Kai. Temporal Knowledge Graph Representation Learning [J]. Computer Science, 2022, 49(9): 162-171.
[2] RAO Zhi-shuang, JIA Zhen, ZHANG Fan, LI Tian-rui. Key-Value Relational Memory Networks for Question Answering over Knowledge Graph [J]. Computer Science, 2022, 49(9): 202-207.
[3] TANG Ling-tao, WANG Di, ZHANG Lu-fei, LIU Sheng-yun. Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy [J]. Computer Science, 2022, 49(9): 297-305.
[4] WANG Jian, PENG Yu-qi, ZHAO Yu-fei, YANG Jian. Survey of Social Network Public Opinion Information Extraction Based on Deep Learning [J]. Computer Science, 2022, 49(8): 279-293.
[5] HAO Zhi-rong, CHEN Long, HUANG Jia-cheng. Class Discriminative Universal Adversarial Attack for Text Classification [J]. Computer Science, 2022, 49(8): 323-329.
[6] JIANG Meng-han, LI Shao-mei, ZHENG Hong-hao, ZHANG Jian-peng. Rumor Detection Model Based on Improved Position Embedding [J]. Computer Science, 2022, 49(8): 330-335.
[7] SUN Qi, JI Gen-lin, ZHANG Jie. Non-local Attention Based Generative Adversarial Network for Video Abnormal Event Detection [J]. Computer Science, 2022, 49(8): 172-177.
[8] HU Yan-yu, ZHAO Long, DONG Xiang-jun. Two-stage Deep Feature Selection Extraction Algorithm for Cancer Classification [J]. Computer Science, 2022, 49(7): 73-78.
[9] CHENG Cheng, JIANG Ai-lian. Real-time Semantic Segmentation Method Based on Multi-path Feature Extraction [J]. Computer Science, 2022, 49(7): 120-126.
[10] HOU Yu-tao, ABULIZI Abudukelimu, ABUDUKELIMU Halidanmu. Advances in Chinese Pre-training Models [J]. Computer Science, 2022, 49(7): 148-163.
[11] ZHOU Hui, SHI Hao-chen, TU Yao-feng, HUANG Sheng-jun. Robust Deep Neural Network Learning Based on Active Sampling [J]. Computer Science, 2022, 49(7): 164-169.
[12] SU Dan-ning, CAO Gui-tao, WANG Yan-nan, WANG Hong, REN He. Survey of Deep Learning for Radar Emitter Identification Based on Small Sample [J]. Computer Science, 2022, 49(7): 226-235.
[13] PENG Shuang, WU Jiang-jiang, CHEN Hao, DU Chun, LI Jun. Satellite Onboard Observation Task Planning Based on Attention Neural Network [J]. Computer Science, 2022, 49(7): 242-247.
[14] WANG Jun-feng, LIU Fan, YANG Sai, LYU Tan-yue, CHEN Zhi-yu, XU Feng. Dam Crack Detection Based on Multi-source Transfer Learning [J]. Computer Science, 2022, 49(6A): 319-324.
[15] CHU Yu-chun, GONG Hang, Wang Xue-fang, LIU Pei-shun. Study on Knowledge Distillation of Target Detection Algorithm Based on YOLOv4 [J]. Computer Science, 2022, 49(6A): 337-344.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!