This paper was first presented in 2013 at the International Conference on Data Engineering (ICDE) in Brisbane; its core ideas are still available as a slide presentation online [1]. Since then, work has gone on following the continuing interest of the Melbourne School of Information in the research area of destination prediction, or the statistical guess of successive locations along the course of a trip. This, beyond the obvious academic interest, is important in many real-world situations, among others the location-based applications currently popular on portable devices. The field is not new, of course, but existing methods rely on proprietary data sources, are difficult and costly to obtain, or depend on series of historical data, which can be severely incomplete.

This version of the paper expands on the original one [2]. At first, it presents a baseline prediction algorithm based on existing works. Then, it enhances it, focusing mainly on how space is subdivided into grids and on how to model trajectories using Markov models. The paper then refines this base algorithm both in terms of runtime efficiency and prediction accuracy, as well as in terms of cost analysis. All of these topics are presented first using rigorous mathematical notation, but their results are soon applied to a large real-world dataset with a live demo website [3], which lets even the casual reader enjoy the results and the significance of the paper.