Research On Algorithms For Mining Group Moving Pattern From Spatio-temporal Trajectories

The increasing availability of location-acquisition technologies including telemetry,GPS set and smart phones results in huge volumes of spatio-temporal trajectories.Analyzing and studying such data provides the opportunity of discovering usable knowledge and hidden patterns about movement behavior.Group moving pattern discovery is an important research topic in the field of spatio-temporal trajectory pattern mining,which can benefit ranges of applications and services,such as urban planning,traffic management,public security and animal migration research.To address these problem in previous works,this thesis studies the algorithm for mining group moving pattern from spatio-temporal trajectories by three different perspectives: movement pattern,movement periodicity and regional mobility.The main innovation contributions of this thesis are as follows:1.Propose algorithm APMine(Aggregation moving Pattern Mining)for mining aggregation moving pattern from spatio-temporal trajectories.Aiming at tracking gathered group,the algorithm can effectively identify group various evolution and movement process in space and time.In the process of pattern mining,cluster similarity relation is utilized to identify the association between groups and variation tendency.Cluster similarity join on adjacent cluster sets is performed to mining aggregation moving pattern.In addition,in order to improve the performance of pattern mining,member relationship between clusters is utilized to filter and prune candidate clusters.Algorithm APMine?PI based on prefix inverted index and APMine?PP based on prefix partition index are proposed to achieve high efficiency.Finally,experiment results show that the improved algorithm APMine?PI and APMine?PP have a better performance than the baseline algorithm APMine clearly.2.Propose algorithm CPMine(Collective Periodic moving pattern Mining)for mining collective periodic moving pattern from spatio-temporal trajectories.The algorithm generates initial candidates by identifying high-density regions,and then adopts a filter-refine paradigm to mining group periodic moving patterns.In the filter phase,it filters the initial candidates generated by sub-patterns,and refines them to determine final results in the refine phase.In order to raise mining efficiency,algorithm CPMine?S is proposed,which develops a pruning algorithm based on spatial proximity to rapidly filter enormous invalid candidates.Moreover,algorithm CPMine?I is further proposed to greatly reduce search space,which devises a specialized index structure and its update algorithm to support more efficient trajectory queries.Finally,experiment results show that the improved algorithm GPMine-IS using pruning and index outperforms the other three algorithms significantly.3.Propose algorithm RPMine(Regional moving Pattern Mining)for mining regional moving pattern from spatio-temporal trajectories.The algorithm discovers the moving patterns between geographical regions caused by the movement behaviors of moving objects.Firstly,the dense areas are identified by using the movement of moving objects in regions.Then,CLIQUE-based region clustering is performed on these dense areas,and the tree structure is used to store OD clusters obtained at different granularities.In order to mine multi-granularity regional movement patterns,a multigranularity regional tree construction algorithm,called Build RT,is proposed to combine regions at different levels and obtain the final patterns.Finally,experiment results verify the effectiveness of algorithm RPMine.