Predicting Routes and Destinations of Urban Trips using PPM Method

  • Francisco N. Neto UFCG/IFPB
  • Cláudio Baptista UFCG
  • Cláudio Campelo UFCG


Information about destination and route that a person will take is important for various purposes, such as to prevent a user going through a congested route. However, an information system where users must explicitly input their intended destination seems not be useful for daily routines. Ideally, the system should be able to predict the destination and the route to be taken by a vehicle as soon as it starts to move. This paper presents a new technique to predict route and destination, based on Prediction by Partial Matching (PPM) compression method. By considering two important contextual information (day of week and time of departure), the results obtained by our approach were encouraging, reaching around 92% of accuracy rate.


Burbey, I. and Martin, T. L. (2008) “Predicting Future Locations Using Prediction-by- Partial-Match”, In: Proc. 1st ACM MELT, pages 1-6.

Chen, L., Lv, M., Ye, Q., Chen, G. and Woodward, J. (2011) “A personal route prediction system based on trajectory data mining”, In: Information Science, pages 1264-1284, Elsevier.

Fei, X., Lu, C. and Liu, K. (2011) “A bayesian dynamic linear model approach for realtime short-term freeway travel time prediction”, In: Transport. Res. Part C, pages 1306-1318, Elsevier.

Krumm, J. (2008) “A Markov Model for Driver Turn Prediction”, In: Society of Automotive Engineers.

Mark, C. D., Sadek, A. W. and Rizzo, D. (2004) “Predicting Experienced Travel Time with Neural Networks: A PARAMICS Simulation Study”, In: Proceeding of 7th International IEEE Conference on Intelligent Transportation Systems.

Morzy, M. (2006) “Prediction of moving object location based on frequent trajectories”, In: ISCIS, p. 583-592, Springer.

Salomon, D. (2004), Data Compression: The Complete Reference. Springer, 3rd Edition, New York, NY.

Simmons, R., Browing, B., Yilu, Z. and Sadekar, V. (2006) “Learning to Predict Driver Route and Destination Intent”, In: Intelligent Transportation Systems Conference.

Tanaka, K., Kihino, Y., Terada, T., and Nishio, S. (2009) “A Destination Prediction Method Using Driving Contexts and Trajectory for Car Navigation Systems”, In: ACM symposium on Applied Computing, pages 190-195.

Xue, A. Y., Zhang, R., Zheng, Y., Xie, X., Huang, J. and Xu, Z. (2013) “Destination Prediction by Sub-Trajectory Synthesis and Privacy Protection Against Such Prediction”, In: International Conference on Data Engineering, pages 254-265.

N. NETO, Francisco; BAPTISTA, Cláudio; CAMPELO, Cláudio. Predicting Routes and Destinations of Urban Trips using PPM Method. In: SIMPÓSIO BRASILEIRO DE COMPUTAÇÃO UBÍQUA E PERVASIVA (SBCUP), 7. , 2015, Recife. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2015 . p. 121-130. ISSN 2595-6183. DOI: