Destination prediction is an essential task in a variety of mobile applications. In this paper, we optimize the matrix operation and adapt a semi-lazy framework to improve the prediction accuracy and efficiency of a state-of-the-art approach. To this end, we employ efficient dynamic-programming by devising several data constructs including Efficient Transition Probability and Transition Probabilities with Detours that are capable of pinpointing the minimum amount of computation. We prove that our method achieves one order of cut in both time and space complexity. The experimental results on real-world and synthetic datasets have shown that our solution consistently outperforms its state-of-the-art counterparts in terms of both efficiency (approximately over 100 times faster) and accuracy (above 30 increase).
The analysis of human location histories is currently getting an increasing attention, due to the widespread usage of geopositioning technologies such as the GPS, and also of online location-based services that allow users to share this information. Tasks such as the prediction of human movement can be addressed through the usage of these data, in turn offering support for more advanced applications, such as adaptive mobile services with proactive context-based functions. This paper presents an hybrid method for predicting human mobility on the basis of Hidden Markov Models (HMMs). The proposed approach clusters location histories according to their characteristics, and latter trains an HMM for each cluster. The usage of HMMs allows us to account with location characteristics as unobservable parameters, and also to account with the effects of each individual's previous actions. We report on a series of experiments with a real-world location history dataset from the GeoLife project, showing that a prediction accuracy of 13.85 can be achieved when considering regions of roughly 1280 squared meters. CrowdPlanner -- a novel crowd-based route recommendation system has been developed, which requests human workers to evaluate candidates routes recommended by different sources and methods, and determine the best route based on the feedbacks of these workers. Our system addresses two critical issues in its core components: a) task generation component generates a series of informative and concise questions with optimized ordering for a given candidate route set so that workers feel comfortable and easy to answer; and b) worker selection component utilizes a set of selection criteria and an efficient algorithm to find the most eligible workers to answer the questions with high accuracy. 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.  The rise of GPS-equipped mobile devices has led to the emergence of big trajectory data. In this paper, we study a new path finding query which finds the most frequent path (MFP) during user-specified time periods in large-scale historical trajectory data. We refer to this query as time period-based MFP (TPMFP). Specifically, given a time period T, a source v_s and a destination v_d, TPMFP searches the MFP from v_s to v_d during T. Though there exist several proposals on defining MFP, they only consider a fixed time period. Most importantly, we find that none of them can well reflect people's common sense notion which can be described by three key properties, namely suffix-optimal (i.e., any suffix of an MFP is also an MFP), length-insensitive (i.e., MFP should not favor shorter or longer paths), and bottleneck-free (i.e., MFP should not contain infrequent edges). The TPMFP with the above properties will reveal not only common routing preferences of the past travelers, but also take the time effectiveness into consideration. Therefore, our first task is to give a TPMFP definition that satisfies the above three properties. Then, given the comprehensive TPMFP definition, our next task is to find TPMFP over huge amount of trajectory data efficiently. Particularly, we propose efficient search algorithms together with novel indexes to speed up the processing of TPMFP. To demonstrate both the effectiveness and the efficiency of our approach, we conduct extensive experiments using a real dataset containing over 11 million trajectories.  The booming industry of location-based services has accumulated a huge collection of users' location trajectories of driving, cycling, hiking, etc. In this work, we investigate the problem of discovering the Most Popular Route (MPR) between two locations by observing the traveling behaviors of many previous users. This new query is beneficial to travelers who are asking directions or planning a trip in an unfamiliar city area, as historical traveling experiences can reveal how people usually choose routes between locations. To achieve this goal, we firstly develop a Coherence Expanding algorithm to retrieve a transfer network from raw trajectories, for indicating all the possible movements between locations. After that, the Absorbing Markov Chain model is applied to derive a reasonable transfer probability for each transfer node in the network, which is subsequently used as the popularity indicator in the search phase. Finally, we propose a Maximum Probability Product algorithm to discover the MPR from a transfer network based on the popularity indicators in a breadth-first manner, and we illustrate the results and performance of the algorithm by extensive experiments. The advances in location-acquisition technologies have led to a myriad of spatial trajectories. These trajectories are usually generated at a low or an irregular frequency due to applications' characteristics or energy saving, leaving the routes between two consecutive points of a single trajectory uncertain (called an uncertain trajectory). In this paper, we present a Route Inference framework based on Collective Knowledge (abbreviated as RICK) to construct the popular routes from uncertain trajectories. Explicitly, given a location sequence and a time span, the RICK is able to construct the top-k routes which sequentially pass through the locations within the specified time span, by aggregating such uncertain trajectories in a mutual reinforcement way (i.e., uncertain + uncertain → certain). Our work can benefit trip planning, traffic management, and animal movement studies. The RICK comprises two components: routable graph construction and route inference. First, we explore the spatial and temporal characteristics of uncertain trajectories and construct a routable graph by collaborative learning among the uncertain trajectories. Second, in light of the routable graph, we propose a routing algorithm to construct the top-k routes according to a user-specified query. We have conducted extensive experiments on two real datasets, consisting of Foursquare check-in datasets and taxi trajectories. The results show that RICK is both effective and efficient. Human behavior is often complex and context-dependent. This paper presents a general technique to exploit this "multidimensional" contextual variable for human mobility prediction. We use an ensemble method, in which we extract different mobility patterns with multiple models and then combine these models under a probabilistic framework. The key idea lies in the assumption that human mobility can be explained by several mobility patterns that depend on a sub-set of the contextual variables and these can be learned by a simple model. We showed how this idea can be applied to two specific online prediction tasks: what is the next place a user will visit? and how long will he stay in the current place?. Using smartphone data collected from 153 users during 17 months, we show the potential of our method in predicting human mobility in real life. 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. Road latent cost, which quantifies how desirable each road is for traveling, is important information to enable many smartcity applications such as route recommendation. Arguably, vehicle trajectories are a good source to learn these costs as drivers intelligently incorporate them into their routing decisions. However, major past approaches misinterpret drivers' behaviors and suffer from trajectory sparsity problem, mainly because they adopt an edge-centric perspective which fails to exploit the sequential information in the entire trajectories. To address these shortcomings, we model drivers' routing decision process which targets at global path optimality, and present a framework to reliably discover those costs by exploiting entire trajectories while isolating the influence of heterogeneous destinations. Extensions are also made to address several issues in practice. Extensive experiments on real world data show that the road costs learned in this way significantly outperform past approaches in several urban computing tasks and require less data for learning.