research-article

Origin-Aware Location Prediction Based on Historical Vehicle Trajectories

Authors:

Xiaohui YuAuthors Info & Claims

ACM Transactions on Intelligent Systems and Technology (TIST), Volume 13, Issue 1

Article No.: 5, Pages 1 - 18

https://doi.org/10.1145/3462675

Published: 29 November 2021 Publication History

Abstract

Next location prediction is of great importance for many location-based applications and provides essential intelligence to various businesses. In previous studies, a common approach to next location prediction is to learn the sequential transitions with massive historical trajectories based on conditional probability. Nevertheless, due to the time and space complexity, these methods (e.g., Markov models) only utilize the just passed locations to predict next locations, neglecting earlier passed locations in the trajectory. In this work, we seek to enhance the prediction performance by incorporating the travel time from all the passed locations in the query trajectory to each candidate next location. To this end, we propose a novel prediction method, namely the Travel Time Difference Model, which exploits the difference between the shortest travel time and the actual travel time to predict next locations. Moreover, we integrate the Travel Time Difference Model with a Sequential and Temporal Predictor to yield a joint model. The joint prediction model integrates local sequential transitions, temporal regularity, and global travel time information in the trajectory for the next location prediction problem. We have conducted extensive experiments on two real-world datasets: the vehicle passage record data and the taxi trajectory data. The experimental results demonstrate significant improvements in prediction accuracy over baseline methods.

References

[1]

Jie Bao, Tianfu He, Sijie Ruan, Yanhua Li, and Yu Zheng. 2017. Planning bike lanes based on sharing-bikes’ trajectories. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 1377–1386.

Digital Library

[2]

Buru Chang, Yonggyu Park, Donghyeon Park, Seongsoon Kim, and Jaewoo Kang. 2018. Content-aware hierarchical point-of-interest embedding model for successive POI recommendation. In Proceedings of the 29th International Joint Conference on Artificial Intelligence. 3301–3307.

Digital Library

[3]

Meng Chen, Yang Liu, and Xiaohui Yu. 2014. NLPMM: A next location predictor with Markov modeling. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. 186–197.

[4]

Meng Chen, Xiaohui Yu, and Yang Liu. 2018. MPE: A mobility pattern embedding model for predicting next locations. World Wide Web 22 (2018), 2901–2920.

[5]

Meng Chen, Xiaohui Yu, and Yang Liu. 2018. PCNN: Deep convolutional networks for short-term traffic congestion prediction. IEEE Transactions on Intelligent Transportation Systems 19, 11 (2018), 3550–3559.

[6]

Meng Chen, Yan Zhao, Yang Liu, Xiaohui Yu, and Kai Zheng. 2020. Modeling spatial trajectories with attribute representation learning. IEEE Transactions on Knowledge and Data Engineering. Early access, June 9, 2020.

[7]

Meng Chen, Yixuan Zuo, Xiaoyi Jia, Yang Liu, Xiaohui Yu, and Kai Zheng. 2021. CEM: A convolutional embedding model for predicting next locations. IEEE Transactions on Intelligent Transportation Systems 22, 6 (2021), 3349–3358.

[8]

Jingze Cui, Xian Zhou, Yanmin Zhu, and Yanyan Shen. 2018. A road-aware neural network for multi-step vehicle trajectory prediction. In Proceedings of International Conference on Database Systems for Advanced Applications. 701–716.

Digital Library

[9]

Xiaoliang Fan, Lei Guo, Ning Han, Yujie Wang, Jia Shi, and Yongna Yuan. 2018. A deep learning approach for next location prediction. In Proceedings of the 22nd International Conference on Computer Supported Cooperative Work in Design. IEEE, Los Alamitos, CA, 69–74.

[10]

Shanshan Feng, Xutao Li, Yifeng Zeng, Gao Cong, and Yeow Meng Chee. 2015. Personalized ranking metric embedding for next new POI recommendation. In Proceedings of the 24th International Conference on Artificial Intelligence. ACM, New York, NY, 2069–2075.

Digital Library

[11]

Chenjuan Guo, Bin Yang, Jilin Hu, Christian S. Jensen, and Lu Chen. 2020. Context-aware, preference-based vehicle routing. VLDB Journal 29, 5 (2020), 1149–1170.

[12]

Dan He, Boyu Ruan, Bolong Zheng, and Xiaofang Zhou. 2018. Origin-destination trajectory diversity analysis: Efficient top-k diversified search. In Proceedings of the 19th IEEE International Conference on Mobile Data Management. IEEE, Los Alamitos, CA, 135–144.

[13]

Jilin Hu, Chenjuan Guo, Bin Yang, and Christian S. Jensen. 2019. Stochastic weight completion for road networks using graph convolutional networks. In Proceedings of the 2019 IEEE 35th International Conference on Data Engineering (ICDE’19). 1274–1285.

[14]

Jilin Hu, Bin Yang, Chenjuan Guo, Christian S. Jensen, and Hui Xiong. 2020. Stochastic origin-destination matrix forecasting using dual-stage graph convolutional, recurrent neural networks. In Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE’20). 1417–1428.

[15]

David Hull. 1993. Using statistical testing in the evaluation of retrieval experiments. In Proceedings of the SIGIR Conference on Research and Development in Information Retrieval. 329–338.

Digital Library

[16]

Tung Kieu, Bin Yang, Chenjuan Guo, and Christian S. Jensen. 2018. Distinguishing trajectories from different drivers using incompletely labeled trajectories. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM’18). 863–872.

Digital Library

[17]

Dejiang Kong and Fei Wu. 2018. HST-LSTM: A hierarchical spatial-temporal long-short term memory network for location prediction. In Proceedings of International Joint Conference on Artificial Intelligence. 2341–2347.

Digital Library

[18]

Defu Lian, Kai Zheng, Yong Ge, Longbing Cao, Enhong Chen, and Xing Xie. 2018. GeoMF++ scalable location recommendation via joint geographical modeling and matrix factorization. ACM Transactions on Information Systems 36, 3 (2018), 1–29.

Digital Library

[19]

Defu Lian, Vincent W. Zheng, and Xing Xie. 2013. Collaborative filtering meets next check-in location prediction. In Proceedings of the 22nd International Conference on World Wide Web. 231–232.

Digital Library

[20]

Qiang Liu, Shu Wu, Liang Wang, and Tieniu Tan. 2016. Predicting the next location: A recurrent model with spatial and temporal contexts. In Proceedings of the AAAI Conference on Artificial Intelligence. 194–200.

Digital Library

[21]

Anna Monreale, Fabio Pinelli, Roberto Trasarti, and Fosca Giannotti. 2009. WhereNext: A location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 637–646.

Digital Library

[22]

Bei Pan, Ugur Demiryurek, and Cyrus Shahabi. 2012. Utilizing real-world transportation data for accurate traffic prediction. In Proceedings of the IEEE International Conference on Data Mining. 595–604.

Digital Library

[23]

Simon Aagaard Pedersen, Bin Yang, and Christian S. Jensen. 2020. Fast stochastic routing under time-varying uncertainty. VLDB Journal 29, 4 (2020), 819–839. https://doi.org/10.1007/s00778-019-00585-6

[24]

Shaojie Qiao, Nan Han, Junfeng Wang, Rong-Hua Li, Louis Alberto Gutierrez, and Xindong Wu. 2017. Predicting long-term trajectories of connected vehicles via the prefix-projection technique. IEEE Transactions on Intelligent Transportation Systems 19, 7 (2017), 2305–2315.

[25]

Yuanyuan Qiao, Zhongwei Si, Yanting Zhang, Fehmi Ben Abdesslem, Xinyu Zhang, and Jie Yang. 2018. A hybrid markov-based model for human mobility prediction. Neurocomputing 278 (2018), 99–109.

[26]

Yuelei Xiao and Qing Nian. 2020. Vehicle location prediction based on spatiotemporal feature transformation and hybrid LSTM neural network. Information 11, 2 (2020), 84.

[27]

Guangtao Xue, Zhongwei Li, Hongzi Zhu, and Yunhuai Liu. 2009. Traffic-known urban vehicular route prediction based on partial mobility patterns. In Proceedings of the International Conference on Parallel and Distributed Systems. 369–375.

Digital Library

[28]

Cheng Yang, Maosong Sun, Wayne Xin Zhao, Zhiyuan Liu, and Edward Y. Chang. 2017. A neural network approach to jointly modeling social networks and mobile trajectories. ACM Transactions on Information Systems 35, 4 (2017), 36.

Digital Library

[29]

Zhong Yang, Bolong Zheng, Guohui Li, Xi Zhao, Xiaofang Zhou, and Christian S. Jensen. 2020. Adaptive top-k overlap set similarity joins. In Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE’20). IEEE, Los Alamitos, CA, 1081–1092.

[30]

Jihang Ye, Zhe Zhu, and Hong Cheng. 2013. What’s your next move: User activity prediction in location-based social networks. In Proceedings of the 2013 SIAM International Conference on Data Mining. 171–179.

[31]

Jin Y. Yen. 1971. Finding the k shortest loopless paths in a network. Management Science 17, 11 (1971), 712–716.

Digital Library

[32]

Hongzhi Yin, Weiqing Wang, Hao Wang, Ling Chen, and Xiaofang Zhou. 2017. Spatial-aware hierarchical collaborative deep learning for POI recommendation. IEEE Transactions on Knowledge and Data Engineering 29, 11 (2017), 2537–2551.

Digital Library

[33]

Fuqiang Yu, Lizhen Cui, Wei Guo, Xudong Lu, Qingzhong Li, and Hua Lu. 2020. A category-aware deep model for successive POI recommendation on sparse check-in data. In Proceedings of the Web Conference. 1264–1274.

Digital Library

[34]

Peisen Yuan, Chaofeng Sha, Xiaoling Wang, Bin Yang, Aoying Zhou, and Su Yang. 2010. XML structural similarity search using MapReduce. In Proceedings of the 11th International Conference on Web-Age Information Management (WAIM’10). 169–181.

Digital Library

[35]

Daqiang Zhang, Shengjie Zhao, Laurence T. Yang, Min Chen, Yunsheng Wang, and Huazhong Liu. 2015. NextMe: Localization using cellular traces in Internet of Things. IEEE Transactions on Industrial Informatics 11, 2 (2015), 302–312.

[36]

Xiaocai Zhang, Zhixun Zhao, Yi Zheng, and Jinyan Li. 2019. Prediction of taxi destinations using a novel data embedding method and ensemble learning. IEEE Transactions on Intelligent Transportation Systems 21, 1 (2019), 68–78.

[37]

Kai Zhao, Denis Khryashchev, and Huy Vo. 2021. Predicting taxi and Uber demand in cities: Approaching the limit of predictability. IEEE Transactions on Knowledge and Data Engineering 33, 6 (2021), 2723–2736.

[38]

Kangzhi Zhao, Yong Zhang, Hongzhi Yin, Jin Wang, Kai Zheng, Xiaofang Zhou, and Chunxiao Xing. 2020. Discovering subsequence patterns for next POI recommendation. In Proceedings of the 29th International Joint Conference on Artificial Intelligence. 3216–3222.

Digital Library

[39]

Pengpeng Zhao, Anjing Luo, Yanchi Liu, Fuzhen Zhuang, Jiajie Xu, Zhixu Li, Victor S. Sheng, and Xiaofang Zhou. 2020. Where to go next: A spatio-temporal gated network for next poi recommendation. IEEE Transactions on Knowledge and Data Engineering. Early access, July 6, 2020.

[40]

Shenglin Zhao, Tong Zhao, Irwin King, and Michael R. Lyu. 2017. Geo-Teaser: Geo-temporal sequential embedding rank for point-of-interest recommendation. In Proceedings of the 26th International Conference on World Wide Web Companion. 153–162.

Digital Library

[41]

W. X. Zhao, N. Zhou, A. Sun, J. Wen, J. Han, and E. Y. Chang. 2017. A time-aware trajectory embedding model for next-location recommendation. Knowledge and Information Systems 56, 477 (2017), 1–21.

Digital Library

[42]

Bolong Zheng, Chenze Huang, Christian S. Jensen, Lu Chen, Nguyen Quoc Viet Hung, Guanfeng Liu, Guohui Li, and Kai Zheng. 2020. Online trichromatic pickup and delivery scheduling in spatial crowdsourcing. In Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE’20). IEEE, Los Alamitos, CA, 973–984.

[43]

Bolong Zheng, Han Su, Wen Hua, Kai Zheng, Xiaofang Zhou, and Guohui Li. 2017. Efficient clue-based route search on road networks. TKDE 29, 9 (2017), 1846–1859.

Digital Library

[44]

Bolong Zheng, Xi Zhao, Lianggui Weng, Nguyen Quoc Viet Hung, Hang Liu, and Christian S. Jensen. 2020. PM-LSH: A fast and accurate LSH framework for high-dimensional approximate NN search. PVLDB 13, 5 (2020), 643–655.

Digital Library

[45]

Bolong Zheng, Kai Zheng, Christian S. Jensen, Nguyen Quoc Viet Hung, Han Su, Guohui Li, and Xiaofang Zhou. 2020. Answering why-not group spatial keyword queries. IEEE Transactions on Knowledge and Data Engineering 32, 1 (2020), 26–39.

[46]

Y. Zheng. 2015. Trajectory data mining: An overview. IEEE Transactions on Intelligent Systems and Technology 6, 3 (2015), 29.

Digital Library

[47]

Jingbo Zhou, Anthony K. H. Tung, Wei Wu, and Wee Siong Ng. 2013. A semi-lazy approach to probabilistic path prediction. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 748–756.

Digital Library

Cited By

Sun TZhao KChen M(2024)Human-AI Interaction: Human Behavior Routineness Shapes AI PerformanceIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.348031736:12(8476-8487)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3480317
Zhang YHuang WYao YGao SCui LYan Z(2024)Urban region representation learning with human trajectories: a multi-view approach incorporating transition, spatial, and temporal perspectivesGIScience & Remote Sensing10.1080/15481603.2024.238739261:1Online publication date: 4-Sep-2024
https://doi.org/10.1080/15481603.2024.2387392
Zhang YYu WZhu D(2024)Next track point prediction using a flexible strategy of subgraph learning on road networksInternational Journal of Geographical Information Science10.1080/13658816.2024.235852738:10(1939-1964)Online publication date: 27-May-2024
https://doi.org/10.1080/13658816.2024.2358527
Show More Cited By

Index Terms

Origin-Aware Location Prediction Based on Historical Vehicle Trajectories
1. Information systems
  1. Information systems applications
    1. Spatial-temporal systems
      1. Location based services

Recommendations

A survey on next location prediction techniques, applications, and challenges
Abstract
Next location prediction has recently gained great attention from researchers due to its importance in different application areas. Recent growth of location-based service applications has vast domain influence such as traffic-flow prediction, ...
Human Mobility Prediction Challenge: Next Location Prediction using Spatiotemporal BERT
HuMob-Challenge '23: Proceedings of the 1st International Workshop on the Human Mobility Prediction Challenge

Understanding, modeling, and predicting human mobility patterns in urban areas has become a crucial task from the perspectives of traffic modeling, disaster risk management, urban planning, and more. HuMob Challenge 2023 aims to predict future movement ...
Location-based big data analytics for guessing the next Foursquare check-ins

Location-based services on GPS-enabled smartphones are undergoing strong growth. Capitalizing on the popularity of this geo-location social media, a mobile app called Foursquare is developed to recommend its users places where they may be interested in, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Intelligent Systems and Technology

ACM Transactions on Intelligent Systems and Technology Volume 13, Issue 1

February 2022

349 pages

ISSN:2157-6904

EISSN:2157-6912

DOI:10.1145/3502429

Editor:
Huan Liu
Arizona State University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 November 2021

Accepted: 01 April 2021

Revised: 01 March 2021

Received: 01 January 2021

Published in TIST Volume 13, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Natural Science Foundation of China
Natural Science Foundation of Shandong Province of China
Young Scholars Program of Shandong University
NSERC Discovery
China Postdoctoral Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
581
Total Downloads

Downloads (Last 12 months)78
Downloads (Last 6 weeks)12

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sun TZhao KChen M(2024)Human-AI Interaction: Human Behavior Routineness Shapes AI PerformanceIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.348031736:12(8476-8487)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3480317
Zhang YHuang WYao YGao SCui LYan Z(2024)Urban region representation learning with human trajectories: a multi-view approach incorporating transition, spatial, and temporal perspectivesGIScience & Remote Sensing10.1080/15481603.2024.238739261:1Online publication date: 4-Sep-2024
https://doi.org/10.1080/15481603.2024.2387392
Zhang YYu WZhu D(2024)Next track point prediction using a flexible strategy of subgraph learning on road networksInternational Journal of Geographical Information Science10.1080/13658816.2024.235852738:10(1939-1964)Online publication date: 27-May-2024
https://doi.org/10.1080/13658816.2024.2358527
Zeng YChen XJin R(2023)Ensemble Active Learning by Contextual Bandits for AI Incubation in ManufacturingACM Transactions on Intelligent Systems and Technology10.1145/362782115:1(1-26)Online publication date: 19-Dec-2023
https://dl.acm.org/doi/10.1145/3627821
Lyu CPande AZhang YGu DMohapatra P(2023)Enabling Fast and Privacy-Preserving Broadcast Authentication With Efficient Revocation for Inter-Vehicle ConnectionsIEEE Transactions on Mobile Computing10.1109/TMC.2023.327521823:4(3309-3327)Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3275218
Castueras CSuarez KSandoval CFestin CTan W(2022)A Location Sensitive and Utility Based Advertising System for Public TransportTENCON 2022 - 2022 IEEE Region 10 Conference (TENCON)10.1109/TENCON55691.2022.9977826(1-6)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TENCON55691.2022.9977826
Ngo QLan DYoon SJung WYoon TYoo D(2022)Companion Mobility to Assist in Future Human Location PredictionIEEE Access10.1109/ACCESS.2022.318631910(68111-68125)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3186319

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents

NODES