Trajectory prediction (TP) is of great importance for a wide range of location-based applications in intelligent transport systems such as location-based advertising, route planning, traffic management, and early warning systems. In the last few years, the widespread use of GPS navigation systems and wireless communication technology enabled vehicles has resulted in huge volumes of trajectory data. The task of utilizing this data employing spatio-temporal techniques for trajectory prediction in an efficient and accurate manner is an ongoing research problem. Existing TP approaches are limited to short-term predictions. Moreover, they cannot handle a large volume of trajectory data for long-term prediction. To address these limitations, we propose a scalable clustering and Markov chain based hybrid framework, called Traj-clusiVAT-based TP, for both short-term and long-term trajectory prediction, which can handle a large number of overlapping trajectories in a dense road network. Traj-clusiVAT can also determine the number of clusters, which represent different movement behaviours in input trajectory data. In our experiments, we compare our proposed approach with a mixed Markov model (MMM)-based scheme, and a trajectory clustering, NETSCAN-based TP method for both short- and long-term trajectory predictions. We performed our experiments on two real, vehicle trajectory datasets, including a large-scale trajectory dataset consisting of 3.28 million trajectories obtained from 15,061 taxis in Singapore over a period of one month. Experimental results on two real trajectory datasets show that our proposed approach outperforms the existing approaches in terms of both short- and long-term prediction performances, based on prediction accuracy and distance error (in km).
Most of the work done in the area of trajectory prediction either use synthetic datasets @cite_28 @cite_40 @cite_6 @cite_13 or real datasets with small to medium numbers of data points @cite_50 @cite_4 @cite_31 . Most of them cannot handle big trajectory datasets. There have been several attempts to demonstrate trajectory prediction on real data having a large number of samples. For example, @cite_14 uses a real dataset consisting of @math million trajectories ( @math million GPS points) as a population, but only small subsets having a maximum @math trajectories are used in their experiments. To the best of our knowledge, the largest real dataset used was in @cite_3 , consisting of @math million GPS points. They utilized @cite_3 the MapReduce model in their implementation to handle large datasets. In this paper, we use the GPS traces of @math taxis in Singapore over a period of one month. We extract @math million passenger trajectories consisting of @math million GPS logs from this data for trajectory prediction task. To the best of our knowledge, this is the first time trajectory prediction task has been performed on such a large number of real-world road network trajectories.
@cite_14 @cite_4 @cite_28 @cite_6 @cite_3 @cite_40 @cite_50 @cite_31 @cite_13
2062231365 1563419623 1977555135 2523438800 2117742206 1982838671 991541073 2107622755
The pervasiveness of mobile devices and location based services is leading to an increasing volume of mobility data.This side eect provides the opportunity for innovative methods that analyse the behaviors of movements. In this paper we propose WhereNext, which is a method aimed at predicting with a certain level of accuracy the next location of a moving object. The prediction uses previously extracted movement patterns named Trajectory Patterns, which are a concise representation of behaviors of moving objects as sequences of regions frequently visited with a typical travel time. A decision tree, named T-pattern Tree, is built and evaluated with a formal training and test process. The tree is learned from the Trajectory Patterns that hold a certain area and it may be used as a predictor of the next location of a new trajectory finding the best matching path in the tree. Three dierent best matching methods to classify a new moving object are proposed and their impact on the quality of prediction is studied extensively. Using Trajectory Patterns as predictive rules has the following implications: (I) the learning depends on the movement of all available objects in a certain area instead of on the individual history of an object; (II) the prediction tree intrinsically contains the spatio-temporal properties that have emerged from the data and this allows us to define matching methods that striclty depend on the properties of such movements. In addition, we propose a set of other measures, that evaluate a priori the predictive power of a set of Trajectory Patterns. This measures were tuned on a real life case study. Finally, an exhaustive set of experiments and results on the real dataset are presented. Advances in wireless and mobile technology flood us with amounts of moving object data that preclude all means of manual data processing. The volume of data gathered from position sensors of mobile phones, PDAs, or vehicles, defies human ability to analyze the stream of input data. On the other hand, vast amounts of gathered data hide interesting and valuable knowledge patterns describing the behavior of moving objects. Thus, new algorithms for mining moving object data are required to unearth this knowledge. An important function of the mobile objects management system is the prediction of the unknown location of an object. In this paper we introduce a data mining approach to the problem of predicting the location of a moving object. We mine the database of moving object locations to discover frequent trajectories and movement rules. Then, we match the trajectory of a moving object with the database of movement rules to build a probabilistic model of object location. Experimental evaluation of the proposal reveals prediction accuracy close to 80 . Our original contribution includes the elaboration on the location prediction model, the design of an efficient mining algorithm, introduction of movement rule matching strategies, and a thorough experimental evaluation of the proposed model. A method for predicting pedestrian movement on the basis of a mixed Markov-chain model (MMM) is proposed. MMM takes into account a pedestrian's personality as an unobservable parameter. It also takes into account the effects of the pedestrian's previous status. A promotional experiment in a major shopping mall demonstrated that the highest prediction accuracy of the MMM method is 74.4 . In comparison with methods based on a Markov-chain model (MM) and a hidden-Markov model (HMM) (i.e., prediction rates of about 45 and 2 , respectively), the proposed MMM-based prediction method is substantially more accurate. This pedestrian-movement prediction based on MMM using tracking data will make it possible to provide so-called "adaptive mobile services" with proactive functions. With the emergence of smartphones and location-based services, user mobility prediction has become a critical enabler for a wide range of applications, like location-based advertising, early warning systems, and citywide traffic planning. A number of techniques have been proposed to either conduct spatio-temporal mobility prediction or forecast the next-place. However, both produce diverse prediction performance for different users and display poor performance for some users. This paper focuses on investigating the effect of living habits on the models of spatio-temporal prediction and next-place prediction, and selects one from these two models for an individual to achieve effective mobility prediction at users’ points of interest. Based on the hidden Markov model (HMM), a spatio-temporal predictor and a next-place predictor are proposed. Living habits are analyzed in terms of entropy, upon which users are clustered into distinct groups. With large-scale factual mobile data captured from a big city, we compare the proposed HMM-based predictors with existing state-of-the-art predictors and apply them to different user groups. The results demonstrate the robust performance of the two proposed mobility predictors, which outperform the state of the art for various user groups. Existing prediction methods in moving objects databases cannot forecast locations accurately if the query time is far away from the current time. Even for near future prediction, most techniques assume the trajectory of an object's movements can be represented by some mathematical formulas of motion functions based on its recent movements. However, an object's movements are more complicated than what the mathematical formulas can represent. Prediction based on an object's trajectory patterns is a powerful way and has been investigated by several work. But their main interest is how to discover the patterns. In this paper, we present a novel prediction approach, namely The Hybrid Prediction Model, which estimates an object's future locations based on its pattern information as well as existing motion functions using the object's recent movements. Specifically, an object's trajectory patterns which have ad-hoc forms for prediction are discovered and then indexed by a novel access method for efficient query processing. In addition, two query processing techniques that can provide accurate results for both near and distant time predictive queries are presented. Our extensive experiments demonstrate that proposed techniques are more accurate and efficient than existing forecasting schemes. Location is a key context ingredient and many existing pervasive applications rely on the current locations of their users. However, with the ability to predict the future location and movement behavior of a user, the usability of these applications can be greatly improved. In this paper, we propose an approach to predict both the intended destination and the future route of a person. Rather than predicting the destination and future route separately, we have focused on making prediction in an integrated way by exploiting personal movement data (i.e. trajectories) collected by GPS. Since trajectories contain daily whereabouts information of a person, the proposed approach first detects the significant places where the person may depart from or go to using a clustering-based algorithm called FBM (Forward-Backward Matching), then abstracts the trajectories based on a space partitioning method, and finally extracts movement patterns from the abstracted trajectories using an extended CRPM (Continuous Route Pattern Mining) algorithm. Extracted movement patterns are organized in terms of origin-destination couples. The prediction is made based on a pattern tree built from these movement patterns. With the real personal movement data of 14 participants, we conducted a number of experiments to evaluate the performance of our system. The results show that our approach can achieve approximately 80 and 60 accuracy in destination prediction and 1-step prediction, respectively, and result in an average deviation of approximately 60 m in continuous future route prediction. Finally, based on the proposed approach, we implemented a prototype running on mobile phones, which can extract patterns from a user's historical movement data and predict the destination and future route. Next location prediction is of great importance for many location based applications. In many cases, understanding the similarity between objects and the similarity between trajectories may lead to more accurate predictions. In this paper, we propose two novel models exploiting these two types of similarities respectively. The first model, named object-clustered Markov model (object-MM), first clusters similar objects based on their spatial localities, and then builds variable-order Markov models with the trajectories of objects in the same cluster. The second model, named trajectory-clustered Markov model (tra-MM), considers the similarity between trajectories, and clusters the trajectories to form the training set used in building the Markov models. The two models are integrated to produce the final next location predictor (objectTra-MM). Experiments based on a real data set demonstrate significant increase in prediction accuracy of objectTra-MM over existing methods. Location prediction has attracted a significant amount of research effort. Given an object's recent movements and a future time, the goal of location prediction is to predict the location of this object at the future time specified. Prior works have elaborated on mining association relationships among regions, in which objects frequently appear, to predict locations. Association relationships among regions are represented as association rules. By exploring association relationships among regions, prior works are able to have a good accuracy for location prediction. However, with a large amount of trajectory data produced, a huge amount of association rules is expected. Furthermore, trajectory data has both the spatial and temporal information. To further enhance the accuracy of location prediction, one could utilize not only spatial information but also temporal information to estimate locations of objects. In this paper, we propose a spatial-temporal trajectory model (abbreviated as STT) to capture movement behaviors of objects. STT is represented as a probabilistic suffix tree with both spatial and temporal information of movements. Note that STT is able to discover sequential traversal relationships among regions and, for each region, STT derives the corresponding probabilities about the time when objects appear. With the nature of probabilistic suffix tree, we could use a compact structure to capture movement behavior of objects compared to association rules proposed. In light of STT, we further propose an algorithm to traverse STT for location prediction. By exploring both the spatial and temporal information of STT, the accuracy of location prediction is improved. To evaluate our proposed STT and prediction algorithm, we conduct experiments on the synthetic dataset generated from real datasets. Experimental results shows that our proposed STT is able to capture both spatial and temporal patterns of movement behaviors and, by exploring STT, our proposed prediction algorithm outperforms existing works.