Research On Query Optimization And Mining Algorithm For Big Trajectory Data

The proliferation of GPS-enabled devices such as smartphones and the prosperity of location-based service have witnessed an unprecedented collection of trajectory data,which has received a growing research interest.This thesis focuses on management and query of trajectory data,feature extraction for check-in data and users'location prediction.How to effectively manage big trajectory data,is a fundemental task to study this kind of data.Learning from users'trajectory data,understanding users'behaviour pattern,is quite useful in intelligent recommendation,route planning and other industrial application.Processing and understanding of trajectory data is a significant task.Compared to normal spatial data,trajectory data has more complex structure which brings many chal-lenges to its management and mining.This thesis conducts a comprehensive study of the trajectory data,including storage and indexing,query optimization,analysis and pro-cessing,mining and understanding of trajectory data.New indexing structure,model and algorithm are proposed to process trajectory big data efficiently and effectively.Specifi-cally,this thesis studies the following aspects.1.Study a trajectory retrieving query,k-TLT,which aims at retrieving the top-k Trajec- tories by Locations and ranking by traveling Time.Given a set Q of query locations, a k-TLT query retrieves top-k trajectories that are close to Q with respect to traveling time.In contrast to existing works which consider only location information,k-TLT queries also consider the traveling time information,which have many applications, such as travel route planning reference and moving object study.To efficiently answer a k-TLT query,we first online compute a list L_qof trajectories for each query location q?Q,such that trajectories in L_qare ranked by their traveling time to q. Based on the online generated lists L_qcorresponding to query locations,a small set of candidate trajectories that are close to Q is selected by iteratively retrieving tra- jectories from lists L_q.Then,the set of candidate trajectories is refined and pruned to determine the top-k trajectories.2.Investigate the problem of spatial keyword range search on trajectories,which is essential to make sense of large amount of trajectory data.To the best of our knowl- edge,this is the first work to systematically investigate range search over trajectories where three important aspects,i.e.,spatio,temporal and textual,are all taken into consideration.Given a query region,a timespan and a set of keywords,we aim to retrieve trajectories that go through this region during query timespan,and con- tain all the query keywords.To facilitate the range search,a novel index structure called IOC-Tree is proposed based on the inverted indexing and Octree techniques to effectively explore the spatio,temporal and textual based pruning techniques.Fur- thermore,this structure can also support the query with order-sensitive keywords.3.Propose a new feature fusion based prediction approach,GALLOP,i.e.,GlobAL feature fused LOcation Prediction for different check-in scenarios.Based on the carefully designed feature extraction methods,we utilize a novel combined prediction framework.Specifically,we set out to utilize the density estimation model to profile geographical features,i.e.,context information,the factorization method to extract collaborative information,and a graph structure to extract location transition patterns of users'temporal check-in sequence,i.e.,content information.Comprehensive experiments on several real-life datasets are conducted to demon-strate the efficiency and effectiveness of our techniques.