Querying, Mining With Applications On Large-Scale Trajectory Data

Trajectories are histories written in space by moving objects during a period of time. Recently, with the popularity of civilian GPS (Global Positioning System) de-vices as well as the development of location-based services and mobile social network, a vast number of trajectories are cumulated every day and in turn serve for various kinds of applications. While people enjoy the unprecedented convenient brought by these new technologies and services related with trajectories, the challenges of manipulating and utilizing the large volume of trajectory data become more and more urgent. How to query these trajectories and how to mine valuable information from these data, have become key topics in spatial data management and spatial data mining. Focusing on the topic of trajectory querying and trajectory mining, this dissertation addresses several im-portant problems such as the querying of k-nearest neighbour of moving objects and tra-jectories, trajectory mapping and map matching, trajectory mining with its applications in ITS (intelligent transportation systems). Besides, we present several real-world sys-tems we built based on the approaches we proposed in this dissertation.These achieve-ments have important academic value and extensive potential applications. Specifically, the main results, contributions and innovations of this dissertation are summarized as follows:1) We present an efficient approximate CkNN (continuous k-nearest neighbour) query algorithm for moving objects in road networks. Existing approaches on kNN query are mainly based on Euclidean distance, which cannot apply to the road network distance. A few recent approaches on CkNN query in road networks suffer from heavy computa-tional cost, thus not work for the on-line situation. Based on the proposed representing set, our method combines the off-line computing and on-line query, hence, enables an efficient real-time on-line query. Furthermore, we provide theoretical analysis on the complexity of the algorithm and the error bound. 2) We define the problem of k-nearest neighbouring trajectories query and turn it into a special case of the general aggregate top-k query problem. We propose an efficient algorithm for top-k query without random accesses and optimize it in terms of access cost and running time. Extensive experiments on both the synthetic data and the real-world data validate the efficiency and effectiveness of the proposed algorithms.3) We propose several pre-processing algorithms for trajectory mining. In order to map the trajectories to the road network, we present a morphological-image-processing-based map segmentation method, which skilfully tackles the segmentation problem in raster-based road networks; We devise an interactive-voting based map matching algo-rithm for low-sampling-rate trajectories, which improves the accuracy of the state-of-the-art method by10%; We propose a multinomial time algorithm for smoothing the wrongly-mapped trajectories, so as to remove the roundabout parts of the trajectories.4) We introduce a smart driving direction service (T-Drive) based on GPS trajectories of taxicabs. Here, we mine the intelligence of the experienced taxi drivers from a large number of taxi trajectories and predict the traffic condition on road surfaces in a future time, so as to provide ordinary drivers with personalized fastest routes. We develop several trajectory mining models and methods in this system (e.g., the landmark graph model, the Variance-Entropy-Based Clustering and the high-order Markov chain based traffic prediction model), and evaluate it with extensive experiments against several baseline methods. The evaluation results validate the advantage and effectiveness of this system.5) We devise a recommendation system (T-Finder) based on the GPS trajectories of taxicabs. First, this recommender provides the taxi drivers with a location, towards which, they are most likely to find a passenger and maximise their profit. Second, it recommends the passengers with locations (in a walking distance) where they can easily find a vacant taxi. We mine the places where taxi drivers often wait for passengers (termed as parking places) from the trajectories of high-profit drivers, and then we build a probabilistic model to analyse the cost and risk for the drivers in terms of different hunting strategies. We evaluate this system with both the real-world data and in-the-field user studies. The evaluation results show the effectiveness and reliability of this system.