Research On Algorithms For Mining Regional Semantic Patterns From Spatiotemporal Trajectories On Cloud Computing

It is possible to collect large-scale spatiotemporal trajectories with the development of wireless communication,positioning technology,and location-based services.The mining of trajectory patterns combined with semantic information has become a new research hotspot in academia.Nowadays research on semantic trajectory pattern mining mainly focuses on global frequent patterns,ignoring patterns that are infrequent globally and frequent in local areas.There are problems in existing semantic trajectory pattern mining,such as large trajectory scale,high time cost of mining algorithm,and difficult evaluation of mining results.This thesis studies the regional semantic pattern mining algorithm for spatiotemporal trajectories on cloud computing.The main contributions of this thesis are as follows:1.An efficient semantic enrichment process framework called SEPHST is proposed.This framework enriches semantic information on spatiotemporal trajectories based on historical semantic trajectories,which avoids repeated enrichment process of spatiotemporal trajectories through comparison.It includes three phases: historical semantic trajectories database construction,spatiotemporal trajectories segmentation and spatiotemporal trajectories matching and enrichment.In the phase of historical semantic trajectories database construction,a spatial index is established to store historical semantic trajectories to improve the efficiency of semantic enrichment process.Experiments with real spatiotemporal trajectories set show that the proposed framework is efficient and efficiency.2.The parallel mining algorithm of the above algorithm called PSEPHST is proposed.This algorithm parallelizes the three stages of the SEPHST framework in turn.In the phase of historical semantic trajectories database construction,Map function segments large-scale historical semantic trajectories,and Reduce function constructs a representative and diverse historical semantic trajectory database.In the phase of spatiotemporal trajectories segmentation,Map function segments large-scale spatiotemporal trajectories,and Reduce function sorts the spatiotemporal sub-trajectory sequences according to the trajectory ID.In the phase of spatiotemporal trajectories matching and enrichment,Map function calculates historical semantic information and geospatial information,and Reduce function matches historical semantic trajectory information to enrich spatiotemporal trajectories.Experimental results show the high scalability and low time cost of the parallelized algorithm.3.An efficient regional semantic pattern mining algorithm called MRSP is proposed.Firstly,MRSP algorithm calculates candidate semantic category sequences through pattern-growth strategy.Then,the promising candidate semantic category sequence clusters based on p Density clustering.In the neighborhood calculation part of p Density clustering,a neighborhood pruning algorithm called NPSP is proposed to reduce candidate neighbor edges.And a neighborhood search algorithm called NSSI is proposed to improve neighborhood search efficiency.Experiments with real trajectories set show that the above algorithm is efficient as existing algorithm and the mining results show that the efficiency of this algorithm is nearly an order of magnitude higher than that of existing algorithms.4.The parallel mining algorithm of the above algorithm called PMRSP is proposed.This algorithm parallelizes the two stages of the MRSP algorithm in turn.In the phase of candidate semantic category sequence calculation,Map function extracts semantic category sequence instances,and Reduce function calculates the support of each semantic category sequence.In the phase of regional semantic pattern recognition,Map function extracts semantic category sequence instances and calculates the density of each semantic category sequence,and Reduce function clusters local frequent regions based on p Density clustering.Experimental results on real datasets show that with the increase of computing nodes,the algorithm proposed in this thesis has good scalability and speedup.