Key Techniques Of Trajectory Data Analysis And Mining

With the rapid deployment of positioning techniques and the prosperous development of both location-based services and mobile social network,massive vehicular and human trajectories are generated day by day.More and more applications(e.g.,popular-path-based navigation,information and advertising delivery,and ride sharing,etc.)are taking advantage of trajectory data analysis and mining to provide better service.Amongst such processes,the key research points and challenges are:(1)Trajectory similarity analysis,i.e.,how to define proper trajectory similarity function,and how to achieve high efficiency on large trajectory datasets.(2)Identification of user trajectories from their social network posts(e.g.microblogs),i.e.,how to identify trajectories of users from massive non-standard microblog content while achieving high quality.(3)Trajectory matching,i.e.,given certain similarity measurement,how to efficiently match user trajectories with similar transportation needs to maximize the overall sharing rate.To summarize,the main contributions of this dissertation are as follows:1.Similarity join-based trajectory analysis:To address the issue that existing functions can not properly measure vehicular trajectory similarity,this dissertation pro-poses an effective bi-directional trajectory similarity function.To improve efficiency,this dissertation devises a "filtering-and-verification" framework based on trajectory sig-natures.Grid-based signature and threshold-aware signature are developed,so that the similarity of signatures are necessary and sufficient conditions of the similarity of trajec-tories,while the cost of the former is cheaper than the latter.In the "filtering" step,this dissertation employs context-based and cost-based strategies to accomplish fast pruning of dissimilar trajectory pairs.In the "verification" step,this dissertation devises signature-based,expansion-based and bound-based techniques to verify candidate similar pairs and achieve high efficiency.2.Microblog-based trajectory identification:the content of microblogs may contain some locational information,the sequence of such locations thus form user trajec-tories.Existing trajectory identification methods can not tolerate non-standard locational expression in microblogs.This dissertation devises a tree index to organize reference locational data and a three-step trajectory identification process.High quality top-k po-sitions of a microblog can be discovered using fuzzy matching;top-k user positions are generated by aggregating top-k positions of multiple microblogs of one user,which form user trajectories and in turn can be used as feedback to improve the quality of top-k positions of each microblog.This dissertation also proposes incremental algorithms to efficiently support updates of microblog and reference locational data.3.Trajectory matching for maximizing sharing rate:based on above studies on similarity join of vehicular trajectories,and identification of user trajectories,this dissertation further studies the matching of users' vehicular trajectories based on certain similarity measurement(i.e.,shared route percentage),to maximize the overall sharing rate.To solve the join-based matching problem,the question is transformed in to the maximized matching of weighted bigraph;an approximate algorithm is developed to achieve high performance while guaranteeing the quality of the solution.To solve the search-based matching problem,expansion-based and best-first strategies are proposed to implement fast lookup of top-k matches.