Abstract
Mobility prediction of vehicles has become a key feature in mobility management in smart cities, mobile computing environments, intelligent transportation systems, vehicular networks, and location-based services. It has several important applications in traffic congestion forecasting, location-based routing protocol designs and targeting advertisements generation, etc. Mobility prediction (aka route prediction) consists of forecasting future routes to be traversed by a vehicle. Several models have been proposed for route prediction. These models are generally probabilistic models (e.g., Markov models) or data mining-based models (e.g., sequential rule-based models), and are trained with historical location data. Although these models were shown to perform well, one important drawback is that they are lossy. In other words, a large amount of information found in the location data is discarded by their training processes. Consequently, these models do not perform well for predicting routes where detailed information is required to perform accurate predictions. Besides, several prediction models assume the Markovian hypothesis that the next location of a user only depends on his/her current location and any previous movement of the user is ignored in prediction. This hypothesis has been employed, such as in Lian et al. (ACM Trans Intell Syst Technol 6:1–27, 2015. https://doi.org/10.1145/2629557), as a simplifying assumption because it allows building models having a small size. However, this assumption is often unrealistic and thus greatly decreases the accuracy of route prediction. Moreover, these models are noise sensitive as they do not tolerate the smallest deviation in location data principally prone to several disturbances and uncertainty issues. To address these limitations, this paper introduces a novel route prediction model named NextRoute. The proposed model is lossless as it compresses location data in a prediction tree without information loss, and it is designed to use all the relevant information contained in the training data to perform prediction. In contrast to some other proposals, NextRoute provides efficient noise tolerance strategy that loosened the similarity measure when matching the current trajectory of vehicle with historical data. An extensive experimental evaluation was conducted with real-world and synthetic datasets providing quite encouraging results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Amirat H, Lagraa N, Fournier-Viger P, Ouinten Y (2017) MyRoute: a graph-dependency based model for real-time route prediction. J Commun 12:668–676. https://doi.org/10.12720/jcm.12.12.668-676
Bejerano G, Yona G (2001) Variations on probabilistic suffix trees: statistical modeling and prediction of protein families. Bioinformatics 17:23–43. https://doi.org/10.1093/bioinformatics/17.1.23
Bhattacharya A, Das SK (2002) LeZi-update: an information-theoretic framework for personal mobility tracking in PCS networks. Wirel Netw 8:121–135. https://doi.org/10.1023/A:1013759724438
Chen L, Lv M, Chen G (2010) A system for destination and future route prediction based on trajectory mining. Pervasive Mob Comput 6:657–676. https://doi.org/10.1016/j.pmcj.2010.08.004
Chen M, Yu X, Liu Y (2015) Mining moving patterns for predicting next location. Inf Syst 54:156–168. https://doi.org/10.1016/j.is.2015.07.001
Cleary J, Witten I (1984) Data compression using adaptive coding and partial string matching. IEEE Trans Commun 32:396–402. https://doi.org/10.1109/TCOM.1984.1096090
Codeca L, Frank R, Engel T (2015) Luxembourg SUMO Traffic (LuST) Scenario: 24 hours of mobility for vehicular networking research. In: Proceedings of 2015 IEEE vehicular networking conference (VNC). IEEE, pp 1–8. https://doi.org/10.1109/VNC.2015.7385539
De Brébisson A, Simon É, Auvolat A et al (2015) Artificial neural networks applied to taxi destination prediction. In: Proceedings of the 2015th international conference on ECML PKDD discovery challenge, vol 1526. CEUR-WS.org, pp 40–51
Deguchi Y, Kuroda K, Shouji M, Kawabe T (2004) HEV charge/discharge control system based on navigation information. In: Proceedings of convergence international congress and exposition on transportation electronics
Deshpande M, Karypis G (2004) Selective Markov models for predicting Web page accesses. ACM Trans Internet Technol 4:163–184. https://doi.org/10.1145/990301.990304
Fournier-Viger P, Gueniche T, Tseng VS (2012) Using partially-ordered sequential rules to generate more accurate sequence prediction. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, Berlin, pp 431–442. https://doi.org/10.1007/978-3-642-35527-1_36
Fournier-Viger P, Gomariz A, Gueniche T et al (2014) SPMF: a Java open-source pattern mining library. J Mach Learn Res 15:3569–3573
Froehlich J, Krumm J (2008) Route prediction from trip observations. In: Proceedings of SAE world congress, vol 2193, p 53. https://doi.org/10.4271/2008-01-0201
Gueniche T, Fournier-Viger P, Tseng VS (2013) Compact prediction tree: a lossless model for accurate sequence prediction. Lect Notes Comput Sci 8347:177–188. https://doi.org/10.1007/978-3-642-53917-6_16
Gueniche T, Fournier-Viger P, Raman R, Tseng VS (2015) CPT+: decreasing the time/space complexity of the compact prediction tree. Lect Notes Comput Sci 9078:625–636. https://doi.org/10.1007/978-3-319-18032-8_49
Helmholz P, Ziesmann E, Robra-Bissantz S (2013) Context-awareness in the car: prediction, evaluation and usage of route trajectories. Lect Notes Comput Sci 7939:413–419. https://doi.org/10.1007/978-3-642-38827-9_30
Jian Pei J, Jiawei Han J, Mortazavi-Asl B et al (2004) Mining sequential patterns by pattern-growth: the PrefixSpan approach. IEEE Trans Knowl Data Eng 16:1424–1440. https://doi.org/10.1109/TKDE.2004.77
Krumm J (2008) A Markov model for driver turn prediction. SAE World Congr. https://doi.org/10.4271/2008-01-0195
Lian D, Xie X, Zheng VW et al (2015) CEPR: a collaborative exploration and periodically returning model for location prediction. ACM Trans Intell Syst Technol 6:1–27. https://doi.org/10.1145/2629557
Marchal F, Hackney J, Axhausen K (2005) Efficient map matching of large global positioning system data sets: tests on speed-monitoring experiment in Zürich. Transp Res Rec J Transp Res Board 1935:93–100. https://doi.org/10.3141/1935-11
McCallum A, Freitag D, Pereira F (2000) Maximum entropy Markov models for information extraction and segmentation. In: Proceedings of the seventeenth international conference of machine learning, pp 591–598
Merah AF, Samarah S, Boukerche A, Mammeri A (2013) A sequential patterns data mining approach towards vehicular route prediction in VANETs. Mob Netw Appl 18:788–802. https://doi.org/10.1007/s11036-013-0459-6
Mikluščák T, Gregor M, Janota A (2012) Using neural networks for route and destination prediction in intelligent transport systems. Commun Comput Inf Sci 329:380–387. https://doi.org/10.1007/978-3-642-34050-5_43
Neto FDN, Baptista CDS, Campelo CEC (2015) Prediction of destinations and routes in urban trips with automated identification of place types and stay points. In: Proceedings of the Brazilian symposium on geoinformatics, pp 80–91
Neto FDN, de Baptista CS, Campelo CEC (2016) A user-personalized model for real time destination and route prediction. In: Proceedings of 2016 IEEE 19th international conference on intelligent transportation systems (ITSC). IEEE, pp 401–407. https://doi.org/10.1109/itsc.2016.7795586
Petróczi AI, Gáspár-Papanek C (2009) Route prediction on tracking data to location-based services. Lect Notes Comput Sci 5733:69–77. https://doi.org/10.1007/978-3-642-03700-9_8
Piorkowski M, Sarafijanovic-Djukic N, Grossglauser M (2009) CRAWDAD dataset epfl/mobility (v. 2009-02-24). CRAWDAD Wirel Netw data Arch. https://doi.org/10.15783/c7j010
Pitkow J, Pirolli P (1999) Mining longest repeating subsequences to predict world wide web surfing. In: Proceedings of the 2nd conference on USENIX symposium on internet technologies and systems, vol 2, p 13
Qiu D, Papotti P, Blanco L (2013) Future locations prediction with uncertain data. Lect Notes Comput Sci 8188:417–432. https://doi.org/10.1007/978-3-642-40988-2_27
Seni G, Elder JF (2010) Ensemble methods in data mining: improving accuracy through combining predictions. Synth Lect Data Min Knowl Discov 2:1–126. https://doi.org/10.2200/S00240ED1V01Y200912DMK002
Simmons R, Browning B, Zhang YZY, Sadekar V (2006) Learning to predict driver route and destination intent. IEEE Intell Transp Syst Conf 2006:127–132. https://doi.org/10.1109/ITSC.2006.1706730
Terroso-Saenz F, Valdes-Vela M, Skarmeta-Gomez AF (2016) Online route prediction based on clustering of meaningful velocity-change areas. Data Min Knowl Discov. https://doi.org/10.1007/s10618-016-0452-3
Torkkola K, Zhang K, Li H et al (2007) Traffic advisories based on route prediction. In: Proceedings of workshop on mobile interaction with the real world, MIRW 2007, pp 33–36
Wang X, Ma Y, Di J et al (2015) Building efficient probability transition matrix using machine learning from big data for personalized route prediction. Procedia Comput Sci 53:284–291. https://doi.org/10.1016/j.procs.2015.07.305
Xue G, Li Z, Zhu H, Liu Y (2009) Traffic-known urban vehicular route prediction based on partial mobility patterns. In: Proceedings of the international conference of parallel distributed systems (ICPADS), pp 369–375. https://doi.org/10.1109/icpads.2009.129
Ye Q, Chen L, Chen G (2008) Predict personal continuous route. In: Proceedings of the IEEE conference of intelligent transportation systems, ITSC, pp 587–592. https://doi.org/10.1109/itsc.2008.4732585
Ziv J, Lempel A (1978) Compression of individual sequences via variable-rate coding. IEEE Trans Inf Theory 24:530–536. https://doi.org/10.1109/TIT.1978.1055934
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Amirat, H., Lagraa, N., Fournier-Viger, P. et al. NextRoute: a lossless model for accurate mobility prediction. J Ambient Intell Human Comput 11, 2661–2681 (2020). https://doi.org/10.1007/s12652-019-01327-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12652-019-01327-w